MHB Induction Proofs & Negative Proofs: Examining POTW 135

AI Thread Summary
The discussion revolves around the challenges of using induction proofs for negative statements, particularly in relation to a specific problem of the week (POTW 135). The initial logic highlights that while the expression 2^{2^x} has only factors of 2, the expression (n + 1)^3 - 1 includes an odd factor, raising questions about the validity of induction in proving impossibilities. A cleaner solution is suggested that avoids induction by demonstrating that y^3 - 1 contains an odd factor regardless of y's parity. The key point is that while negative predicates can be used in induction, the failure of the inductive step, as illustrated by the example of proving n ≠ 3, is what complicates these proofs. Ultimately, the discussion emphasizes the importance of a valid inductive step rather than the nature of the predicate itself.
topsquark
Science Advisor
Homework Helper
Insights Author
MHB
Messages
2,020
Reaction score
843
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 [math]2^{2^x}[/math] can only have factors of 2. But [math](n + 1)^3 - 1[/math] 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
 
Physics news on Phys.org
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$.)
 

Similar threads

Replies
6
Views
2K
Replies
1
Views
1K
Replies
7
Views
903
Replies
7
Views
1K
Replies
10
Views
3K
Back
Top