uncomfortable with induction hypothesis...

• Oct 13th 2006, 09:30 PM
yc6489
uncomfortable with induction hypothesis...
Hi guys, I'm totally new to number theory, so bear with me...

I'm only on page 2 of the textbook and am already stuck :(

To prove 1+2+3.... +n = n(n+1)/2, we are supposed to assume 1+2+3...+k = k(k+1)/2 for n<=k, and then add k+1 to both sides, etc. etc.

Okay, isn't that first assumption the very statement that we are trying to prove, except replacing n with k? Can someone enlighten me as to how this makes sense?
• Oct 13th 2006, 11:29 PM
CaptainBlack
Quote:

Originally Posted by yc6489
Hi guys, I'm totally new to number theory, so bear with me...

I'm only on page 2 of the textbook and am already stuck :(

To prove 1+2+3.... +n = n(n+1)/2, we are supposed to assume 1+2+3...+k = k(k+1)/2 for n<=k, and then add k+1 to both sides, etc. etc.

Okay, isn't that first assumption the very statement that we are trying to prove, except replacing n with k? Can someone enlighten me as to how this makes sense?

The general form of an induction proof of a statement S(N) about a natural
number N is:

1. Show S(N0) is true for some initial N=N0, this is called the base case
and N0 is often 0 or 1.

2. Show that if S(k) is true for some natural number k, then it is also
true for k+1.

3. Then as it is true for N0, it is true for N0+1, and then for N0+2, and so
on, so we conclude that for any natural number N>N0 it is true, as we can
connect it to the base case by a chain of step 2 above.

4. As we now have that S(N) is true for any natural N>=N0, we conclude
that it is true for all naturals >= N0.

Now your problem is to prove:

1+2+3.... +n = n(n+1)/2

for all natural numbers this is our statement S(n). We take as our base case
n0=1, when S(1) is the assertion:

1 = 1(2)/2 = 1,

which is true, so our base case is true.

Now we assume that S(k) is true for some k and show it true for k+1.
As we are assuming S(k) is true this is the assumption that:

1+2+3.... +k = k(k+1)/2.

Now add (k+1) to each side:

1+2+3.... +k+(k+1) = k(k+1)/2 + (k+1).

Rearrange the right hand side of this equation:

1+2+3.... +k+(k+1) = (1/2)k^2 + (3/2)k +1

..........................= (k+1)(k+2)/2

..........................= (k+1)[(k+1) + 1]/2.

But this equation is now S(k+1), which is:

1+2+3.... +(k+1) = (k+1)[(k+1)+1)/2.

So from the assumption that S(k) was true we have shown that S(k+1)
must also be true, combining this with the base case S(1) which we have
already shown to be true we may conclude by induction that S(n) is true
for all natural numbers n>=1.

RonL