Page 1 of 1

Mathematical Induction Contradiction

Posted: Tue Aug 07, 2012 9:22 pm
by simpleman
Hi,

Can anyone help me understand where I am misunderstanding the principles of induction? I am trying to understand induction by using it to prove a statement is false (below) but I am not "getting it".

Here is the principle of Mathematical Induction (from http://www.math.toronto.edu/oz/turgor/Induction.pdf) and below it is my contradicting rationale:
Principle of Mathematical Induction
If it is known that
(1) some statement is true for n = 1
(2) assumption that statement is true for n implies that
(n + 1)
then the statement is true for all positive integers
Here are my thoughts going through this step by step. Please help point out where my logic is flawed:
step 1
create a statement that is true for n=1:
ok here is my statement that I created to test this out:
for all non-negative integers, 1+2+3+...n =< 2n
for n=1, this statement holds true

step 2
assume that if statement is true for n, then it is true for n+1
ok so the statement is also true for the new "n", which is 2. supposedly this statement should be true for all positive integers based on the above principle of mathematical induction

contradiction
what if n=4? the statement is now false. but according to my understanding of induction, it should be true for any positive integer...
Thank you so much

Posted: Wed Aug 08, 2012 10:08 am
by stapel_eliz
step 2
assume that if statement is true for n, then it is true for n+1
ok so the statement is also true for the new "n", which is 2. supposedly this statement should be true for all positive integers based on the above principle of mathematical induction
You assumed that, if the statement is true for n, then it must be true for n + 1. But that's exactly what you're supposed to prove.

All you're supposed to assume is that the statement is true for some n (or, more usually, some k). Then you have to prove that it's true for some n + 1.

You can learn how this works in this article. I think you'll find the second page to be the most useful. :wink:

Re: Mathematical Induction Contradiction

Posted: Thu Aug 09, 2012 4:57 am
by simpleman
Thank you very much.

Link to a very similar thread I started: viewtopic.php?f=15&t=2675 which may also be helpful to anyone with similar questions