Subsection 8.3.9 When Should We Try a Proof by Contradiction?
Given something that we want to prove, how do we know to try a proof by contradiction (an indirect proof)? One way is to try to write a direct proof and discover that we’re not making much progress.
Suppose that we want to prove:
[1] For all integers n, if n2 is even, then n is also even.
Sometimes it’s enlightening to write our claim in our formal logical notation. We can do that here:
[1'] \(\forall\) n (Even(n2) \(\rightarrow\) Even(n))
We might first try to prove this claim directly. From the definition of Even, we have, since we can assume that n2 is even, that there exists some integer k such that:
[2] \(n^2 = 2k \)
We’re interested in n. So we take the square root of both sides and we get:
[3] n = √2k
But now we’re sort of stuck.
When we get stuck like this, it often makes sense to try an indirect proof.
We’ll assume that the implication is false, namely that, for some n, n2 is even but n is not even. In other words, n is odd, so there exists some integer k such that:
[4] n = 2k + 1
Squaring both sides, we have:
[5] n2 = (2k + 1) (2k + 1)
Doing some simple algebra, we have:
[6] n2 = 4k2 + 2k + 2k + 1
= 4k2 + 4k + 1
= 2 (2k2 + 2k) + 1
But a number is odd just in case it is 1 more than some number that is divisible by 2. So we have that n2 is odd. But that contradicts our starting premise that n2 was even. Thus the assumption that n is not even must be false. So n is even.
Exercises Exercises
1.
Let n be any positive integer. Prove that, if n is a perfect square, n + 2 is not a perfect square.
If n is a perfect square, then there exists some integer i such that:
We have that, if n is a perfect square, then there exists some integer i such that:
Now suppose, contradicting our claim, that n + 2 is a perfect square. Then there exists some integer j such that:
We now have two expressions that are equal to n + 2. Set them equal to each other and see what happens.
We have that, if n is a perfect square, then there exists some integer i such that:
Now suppose, contradicting our claim, that n + 2 is a perfect square. Then there exists some integer j such that:
So we have:
Now factor the left hand side. And notice that 2 has only two factors, 1 and 2. So what must be the values of the two factors of the left hand side?
We have that, if n is a perfect square, then there exists some integer i such that:
sNow suppose, contradicting our claim, that n + 2 is a perfect square. Then there exists some integer j such that:
So we have:
2 has only two factors, 1 and 2. There are two cases:
For each case, add the two equations. Do you get a contradiction with the assumption that j is an integer?
We have that, if n is a perfect square, then there exists some integer i such that:
Now suppose, contradicting our claim, that n + 2 is a perfect square. Then there exists some integer j such that:
So we have:
2 has only two factors, 1 and 2. There are two cases:
In each case, we add the two equations:
But, in both cases, we get that j = 3/2, contradicting the assumption that j is an integer. So our assumption that (n + 2) is a perfect square must be false.