Expert: Paul Klarreich - 5/19/2007

Question
Hi i am really stuck on these questions. Can you show me how they are done?
1. Use induction to prove that for any real number a>=0:(1+a)^n>=(1+na) for all n>=1.
2. Prove by induction that:
1x2+2x3+...+n(n+1)=1/3n(n+1)(n+2)
for all integers n>0.


Answer
Questioner:   scott
Category:  Advanced Math
 
Question:  Hi i am really stuck on these questions. Can you show me how they are done?
1. Use induction to prove that for any real number a>=0:(1+a)^n>=(1+na) for all n>=1.
2. Prove by induction that:
1x2+2x3+...+n(n+1)=1/3n(n+1)(n+2)
for all integers n>0.
.........................................
Hi, Scott,

When you proved something by M.I. you proceed:

A. Verify the theorem for the base case, which is usually  n = 1, but it doesn't have to be.
B. Write the theorem out for the case  n = k.  Make this your ASSUMPTION.
C. Write the theorem out for the case  n = k+1.  Prove this.  At some point in your proof, make use of the ASSUMPTION.  

For a >= 0:  (1+a)^n  >=  (1+na) for all n >= 1.

A.  (1 + a)^1 = 1 + a = 1 + (1)a.  We have proved it, using n=1, and in this case, we have "=", not just  >=.

B.  (1 + a)^k >= 1 + ka.  ASSUMPTION.

C. To prove:  (1 + a)^k+1 >= 1 + (k+1)a

Proof:  Try somehow to get  (1 + a)^k to show up.

(1 + a)^k+1 = (1 + a)^k (1 + a)

Use the ASSUMPTION to replace (1+a)^k:

(1 + a)^k (1 + a) >= (1 + ka)(1 + a) =

1 + ka + a + ka^2 =

1 + (k + 1)a + ka^2 >= 1 + (k + 1)a, because  ka^2 >= 0
and that's it.
............................................

2. Prove by induction that:

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

*********** VIEW THIS IN COURIER FONT *********

I assume you mean:
                          n(n+1)(n+2)
1*2 + 2*3 + ... + n(n+1) = -----------
                               3

OK. This may be messy, but I think it is routine.

for all integers n>0.

A. Write the theorem for  n = 1:
     1(1 + 1)(1 + 2)
1*2 = ---------------
            3
and verify it:

    1(2)(3)
2  = --------
       3

     6
2  = --- = 2
     3
OK.

B. Write the theorem for  n = k:

                          k(k+1)(k+2)
1*2 + 2*3 + ... + k(k+1) = -----------  
                               3
That's your ASSUMPTION.

C. Write the theorem for  n = k+1.  This requires nothing more than a little care and a lot of parentheses -- make sure your computer has a good supply.  You can get them at Staples.

To prove:

                                  (k+1)((k+1)+1)((k+1)+2)
1*2 + 2*3 + ... + (k+1)((k+1)+1) = -----------------------  
                                            3
which we can simplify a bit:

                              (k+1)(k+2)(k+3)
1*2 + 2*3 + ... + (k+1)(k+2) = ---------------
                                      3
<< ------ LEFT SIDE ----->>    << RIGHT SIDE >>


Proof: Try to get the left side of the assumption to show up. But the left side of the 'to prove' contains the left side of the assumption, plus an extra term:

1*2 + 2*3 + ............ + (k+1)(k+2) =
1*2 + 2*3 + ... + k(k+1) + (k+1)(k+2) = (by assumption)

k(k+1)(k+2)
-----------  + (k+1)(k+2)
     3
Now all you have to do is work out the algebra to show that this is the same as the RIGHT SIDE.  It can go this way:

Combine fractions over an LCD of 3:

k(k+1)(k+2) + 3(k+1)(k+2)   << common factor of (k+1)(k+2)
-------------------------
         3
(k+3)(k+1)(k+2)     << take out that common factor
----------------
       3

This is the same as the RIGHT SIDE.  Q.E.D., as they say.

Induction is fun.