Indirect Proof

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’ are 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.


---------------------------------------------------------------------------------------------------------

Listed below are more articles related to the above article from the "Reference And Education" article category.

People interested in the above article "Indirect Proof" are also interested in the related articles listed below:

 

7 Reasons Why Universities Should Make Textbooks Available on eBook Readers

There are numerous Universities and Libraries now researching how to revolutionize the way people read and study. The eBook Reader, an electronic device that can easily be carried with an individual like a traditional book, is an integral part of this cutting-edge technology. A look is taken here at several reasons why the Universities should consider converting textbooks to eBook Readers.

How To Become BPI-Certified

The job market in the United States is as tough as it has been in years, with most job sectors decreasing at numbers unforeseen before. However, one sector of the economy that is exploding and experiencing exponential job growth is green energy. For someone looking for a new start or looking to supplement their skills to make themselves more marketable, the natural question is how can you capitalize on this growing field?

CLEP Study Makes It Easier to Pass Your Examination

It once was that students would earn credits for college through traditional methods of attending classes on campus or even online. However, recent changes have made it easier for students from high school or even more non-traditional students to earn college credits through advanced placement testing or CLEP testing. These testing for college credit methods have gained so much popularity with students and educators alike that now over 2,900 accredited colleges and universities allow students to gain college credits this way.

Memorial Day - Salute to Nation

A day for paying tribute and honor, for soldiers who sacrificed their lives for our country, America. It`s a time and day of dedication where friends and family come together to prepare for the honorary events that serves as a true reminder of Memorial Day.

Courses in Travel and Tourism

Travel and Tourism is a vast industry spanning across the globe. It provides employment to millions of people worldwide and is the major foreign exchange spinner for countries. In India too, the travel and tourism industry is a major one and is fast picking up now with India being promoted as a leisure travel destination by the government.

How to Tell if Your Child Needs a Math Tutor

Math is a tough subject. If one or more of your children are currently taking math classes, you may or may not need a tutor to help them excel in this challenging subject. To help you determine whether it’s right for you, let’s take a look at some signs that they may need help.

Why Prepare for the CLEP Exam

Whether you are about to embark upon your college career or are returning to complete a degree, undertaking a program of CLEP study in preparation for the exam can be very beneficial. CLEP testing can yield considerable savings in time and money students of any age will appreciate.