Can one use mathematical induction to disprove a statement?

[simpleman]

I have a textbook and have researched several websites and have found numerous examples of induction to proving statements are always true, but no examples where induction proves a statement false (except where n=1 (or the base case) is false). Can induction even prove a statement is false (when the base case is true)?

For example, what about the classic false statement:

"2^n - 1 is always a prime number"
base case, 1, results in 1 (prime, so true)
next case, 2, results in 3 (prime, so true)
... ... ...
next case, 11, results in 2047 (not prime (23*89=2047), so false)

Can the inductive method prove this is false? If so, I would love understand, or If not, how is induction a useful at all?

[nona.m.nona]

I have a textbook and have researched several websites and have found numerous examples of induction to proving statements are always true, but no examples where induction proves a statement false (except where n=1 (or the base case) is false). Can induction even prove a statement is false (when the base case is true)?

The difference between "proving a statement is false" and "failing to prove a false statement" is vast. Induction is not constructed to do the former, but the online lesson (in the link in your other thread) shows examples of the latter.

For example, what about the classic false statement:

"2^n - 1 is always a prime number"
base case, 1, results in 1 (prime, so true)
next case, 2, results in 3 (prime, so true)

The ''next'' step would not be "2" but rather "assume, for n = k":

For n = k, assume that 2^k - 1 is a prime number.

Then one would attempt to prove the statement for n = k + 1:

Let n = k + 1. Then...

This would lead either to a contradiction (so the proof fails) or else "nowhere" (so the proof is not completed). (I suspect the attempt would lead "nowhere".) The actual proof (or, in this case, the disproof) is in your specific example of where the statement is false.

[simpleman]

Nona, thank you so much.

Today I looked at that link http://www.purplemath.com/modules/inductn2.htm, which was in fact more explanatory than anything I could find, and wrote out the proof they were doing on my notepad. This helped and I realized something which I think was doing incorrectly that had contributed to my confusion. Please follow below and let me know if you think I'm on the right track:

For the statement: 1+2+...n = (n)(n+1)/2
and (for thoroughness): 1+2+...k = (k)(k+1)/2
when substituting n=k+1
on the Left Hand Side: [1+2+...k] + (k+1),
the link helped me to realize that for this part of the equation: [1+2+...k], we use the right hand side of the ORIGINAL statement as a substitute: 1+2+...k = [(k)(k+1)/2]

After writing the proof above myself, I then tried to prove a different statement, this time one which I know does not hold true for all natural numbers, but holds true for at least some base case:

statement: 1+2+...n = (n^2)-n+1
test case: n=1, --> LHS = 1; RHS = 1 --> TRUE.
let n = k+1 -->
LHS = [1+2+...k] + (k+1)
LHS = [(k^2) - k + 1] + (k+1)
LHS = (k^2) + 2 --> simplified.
RHS = ((k+1)^2) - (k+1) + 1
RHS = ((k^2) + 2k + 1) - k
RHS = (k^2) + k + 1 --> simplified.
As can be seen, the simplified LHS does not equal the simplified RHS. Thus, the inductive method cannot prove this statement to be true for all natural numbers. Not that it proves the statement to be false, but since it cannot prove the statement to be true, I take it that I can safely say it is not true for all natural numbers.

Am I right? Is this sound logic? If so, my next step will be to learn more types of induction proofs, including some of the examples I wanted to prove earlier (inequality statements and statements which say that the result will always be prime). Hopefully I'm ready to move forward! thanks so much, I really appreciate your help

[nona.m.nona]

statement: 1+2+...n = (n^2)-n+1
test case: n=1, --> LHS = 1; RHS = 1 --> TRUE.
let n = k+1 -->
LHS = [1+2+...k] + (k+1)
LHS = [(k^2) - k + 1] + (k+1)
LHS = (k^2) + 2 --> simplified.
RHS = ((k+1)^2) - (k+1) + 1
RHS = ((k^2) + 2k + 1) - k
RHS = (k^2) + k + 1 --> simplified.
As can be seen, the simplified LHS does not equal the simplified RHS. Thus, the inductive method cannot prove this statement to be true for all natural numbers. Not that it proves the statement to be false, but since it cannot prove the statement to be true, I take it that I can safely say it is not true for all natural numbers.

The assumption step, for n = k, appears to have been omitted in the above.

After stating the base case (here, the case for n = 1), it is then necessary to make the initial assumption:

For n = k, assume that 1 + 2 + 3 + ... + (n - 1) + n = n² - n + 1.

Only then does one move on to the inductive step. One may use the "n = k" assumption only if one has stated (has explicitly made) that assumption.

In what you have posted, the work is correct but incomplete. You move from "LHS: k² + 2 and RHS: k² + k + 1" to "LHS does not equal RHS", but do not justify this move. For completeness, it is necessary that you prove that "2" does not equal "k + 1". Since your base step was for "n = 1", then you need only add that your "n = k" assumption step is "for k a natural number, k > 1". Then, since k > 1, then k > 2, so k² > 4, and the conclusion follows.

[simpleman]

Thank you so much. It appears that I am starting to "get" it, but I also need to be more thorough in these proofs; I'll work on that.