Induction Proofs & Negative Proofs: Examining POTW 135

[topsquark]

This is in reference to a POTW, http://mathhelpboards.com/potw-secondary-school-high-school-students-35/problem-week-135-october-27th-2014-a-12786.html.

The logic behind this problem is simple, the number \(\displaystyle 2^{2^x}\) can only have factors of 2. But \(\displaystyle (n + 1)^3 - 1\) contains an odd factor. Great. Works for me.

But how can we consider an induction on this? Every induction proof I've ever run across starts with a "positive" statement... there is some number k such that the statement holds. How can we do an induction that starts with the statement "This is not possible" and continues with "Therefore this other case can't hold either."

As a (ridiculous) example of this, take the statement "x is equal to 3." Base case: k = 1: Thus k is not equal to 3. Induction case: k + 1 is also not equal to three. Thus there is no case that x = 3.

I understand that the above "proof" is, as I said, ridiculous. But it strikes to the heart of my confusion. How do we eliminate "negative proofs" of this kind in general?

-Dan

 

[magneto1]

In reference to the POTW, a cleaner solution would probably be to show $y^3 - 1 = (y - 1)(y^2 + y + 1) $ contains an odd factor regardless the parity of $y$. This get rid of the need of induction.

However, the principle of induction is just for a predicate, or property, $P(x)$ to hold for $P(0)$ and that $P(k) \Rightarrow P(k+1)$. $P$ in this case can certainly be a negative statement.

The problem of the induction "proof" of $n \neq 3$ for all $n \in \Bbb{N}$ is not because the predicate $P(x)$ is negative. It is that the inductive step fails. If $n \neq 3$, there is no logical step that will lead to the conclusion of $n + 1 \neq 3$. (It is false for $n = 2$.)