Indirect Proof

By Chandrajeet K

The concept of proof is an important part of mathematics. There are three basic types of proofs: direct proofs, indirect proofs, and proofs by contradiction.

In this article, let’s learn about Indirect Proof. Please take time and read it carefully till the end.

Indirect proof is a type of proof that begins by ASSUMING what is to be proved is FALSE. Then we try to prove that our ASSUMPTION is true. If our ASSUMPTION leads to a contradiction then the original statement which was assumed false must be true.

Let me explain more in detail.

Suppose you wish to prove ‘statement A’ is true using an indirect proof.

The first thing you do is:

You assume statement A is false…and assume statement A’ which is a contrary of statement A to be true.

Then using valid arguments, you arrive at a contradiction (denial or disagreement) to statement A’.

Thus demonstrating that statement A is true.

This concept will be clearer when you look at some examples.

Example 1

Sarah left her house at 9:30 AM and arrived at her aunt’s house 80 miles away at 10:30 AM. Use an indirect proof to show that Sarah exceeded the 55 mph speed limit.

Solution

Suppose that the given statement is false. That is: ‘Sarah did NOT exceed the 55 mph speed limit.

She drove 80 miles at 55 mph.

At this speed, Sarah would need 80/55 (approximately) = 1 hour 27 minutes to reach her aunt’s place.

But as per the problem she drove from 9:30 AM to 10:30 AM … exactly an hour.

SO, she must have driven faster than 55 mph….a contradiction to our assumption that Sarah did NOT exceed the speed limit.

Therefore, Sarah exceeded the speed limit.


Example 2

Prove the following using an indirect proof.
For all integers ‘n’, if 3n + 1 is even, then ‘n’ is odd.

Solution

Suppose that the conclusion is false. That is: ‘n’ is NOT odd.
Assume the contrary is true. That is: ‘n’ is even.
Then the statement contrary of the given statement is:

“For all integers ‘n’, if 3n + 1 is even, then ‘n’ is EVEN”

Let’s try to prove it.

‘n’ is even means ‘n’ is a multiple of 2…that is: n = 2m for some integer ‘m’.

Then:

3n + 1 = 3(2m) + 1 = 6m + 1 --- Call it Equation (1)
Well…6m is even. So, 6m + 1 is odd.
Therefore, 3n + 1 is ODD…because 3n + 1 = 6m + 1 from Equation (1).

By assuming ‘n’ is even, we’ve shown that 3n + 1 is ODD which is a contradiction to our assumption.

Therefore:

If ‘n’ is odd then 3n + 1 is even. This is the contrapositive of the statement to be proved.

Since the contrapositive is true, it follows that the original statement “if 3n + 1 is even, then ‘n’ is odd” is true.

The next example is a classic problem where an Indirect Proof is used.

Example 3
Prove that square root of 2 or SQRT (2) is irrational using an indirect proof.

Solution
ASSUME that the given statement is false.

That is:

SQRT(2) is NOT irrational.

Assume the contrary to be true…that is…SQRT(2) is RATIONAL.

Let’s try to prove it.

A rational number is a real number that can be expressed as a quotient of two integers a/b, where b does not equal 0.

We’ve assumed SQRT(2) to be a rational number.

So:

SQRT (2) = a/b. This fraction a/b is in lowest terms - that is, a and b have no common factors.

Multiply each side by ‘b’ to get rid of the fraction.

b × SQRT(2) = a
Square both sides.

SQR (b) × 2 = SQR (a) which is the same as:
2 SQR (b) = SQR (a) --- call it Equation (2)

SQR (a) is even…because from Equation (2) above, we have, SQR(a) = 2 SQR(b)…a multiple of 2.

SQR(a) is even…implies…’a’ is even. Then, a = 2k for some integer ‘k’.

Substitute a = 2k in Equation (2). We get:

2 SQR (b) = SQR (a) --- Equation (2)
2 SQR (b) = SQR (2k)
2 SQR (b) = 4 SQR (k)

Cancel ‘2’ on either side. We have:

SQR (b) = 2 SQR (k)

The above equation shows that ‘SQR(b)’ is even…because SQR(b) = 2 SQR(k).

Again, SQR (b) is even implies ‘b’ is even.
If ‘a’ and ‘b’ is both even, then they will have a common factor…

Then…how can the fraction a/b be in lowest terms?
A contradiction…

SO, SQRT (2) is IRRATIONAL.

Example 4

Prove that “For all integers ‘n’, if ‘n’ is odd then SQR(n) is odd” using an indirect proof.

Solution

Suppose the conclusion is false.

That is:

SQR(n) is NOT odd.

ASSUME the contrary… SQR (n) is even.
Then the statement contrary of the given statement is:

“For all integers ‘n’, if ‘n’ is odd then SQR(n) is even”

Let’s try to prove it.

If SQR(n) is even, then SQR(n) can be expressed as a multiple of 4.

So:

SQR (n) = 4k for some integer ‘k’.
Take square root on either sides of the equation. We get:
n = 2 SQRT (k)

The above equation shows that ‘n’ is even, because ‘n’ is a multiple of 2…

By assuming ‘SQR(n)’ is even, we’ve shown that ‘n’ is EVEN which is a contradiction to our assumption.

So:

If ‘SQR(n)’ is odd then ‘n’ is odd. This is the contrapositive of the statement to be proved.

Since the contrapositive is true, it follows that the original statement “If ‘n’ is odd then ‘SQR (n)’ is odd” is true.