MHB Induction Proofs & Negative Proofs: Examining POTW 135

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$.)
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

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