Can one use mathematical induction to disprove a statement?

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
simpleman
Posts: 6
Joined: Tue Aug 07, 2012 8:42 pm
Contact:

Can one use mathematical induction to disprove a statement?

Postby simpleman » Wed Aug 08, 2012 1:23 am

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
Posts: 272
Joined: Sun Dec 14, 2008 11:07 pm
Contact:

Re: Can one use mathematical induction to disprove a stateme

Postby nona.m.nona » Wed Aug 08, 2012 10:52 am

simpleman wrote: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.

simpleman wrote: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 2k - 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
Posts: 6
Joined: Tue Aug 07, 2012 8:42 pm
Contact:

Re: Can one use mathematical induction to disprove a stateme

Postby simpleman » Thu Aug 09, 2012 5:02 am

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
Posts: 272
Joined: Sun Dec 14, 2008 11:07 pm
Contact:

Re: Can one use mathematical induction to disprove a stateme

Postby nona.m.nona » Thu Aug 09, 2012 11:36 am

simpleman wrote: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 = n2 - 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: k2 + 2 and RHS: k2 + 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 k2 > 4, and the conclusion follows.

simpleman
Posts: 6
Joined: Tue Aug 07, 2012 8:42 pm
Contact:

Re: Can one use mathematical induction to disprove a stateme

Postby simpleman » Fri Aug 10, 2012 5:48 am

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.


Return to “Discrete Math”