Induction Problem

Date: 10/14/97 at 20:30:20
From: sharon wesolowski
Subject: Induction

Hi, 

I am having a problem with the reasoning of the left side of an 
induction problem. Here's the original problem:

Use math induction to prove that

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

This is what I have done:

p(k) = (6)^2 = 36

 n^2 = [(n)(n+1)(2n+1)]/6{p} = {pk} [n^2(n+1)^2]/4
            [k(k+1)(2k+1)}/6 = [k^2(k+1)^2]/4
                        Pk+1 = [(k+1)^2(k+2)^2/4
                             = (4k-3) + (4k+1)

Here I am stuck. Is the basis right? How do I match the right and the 
left? Thanks.

Sharon W.

Date: 10/15/97 at 18:56:38
From: Doctor Tom
Subject: Re: Induction

Hi Sharon,

There are a couple of ways to do this. What you seem to be doing is 
the fastest, assuming that you already know how to add up the cubes of 
the numbers to get 1^3 + ... + n^3 = [n^2(n+1)^2]/4.

If you know that, and you also know that 1 + 2 + ... + n = n(n+1)/2,
then squaring that value obviously gives you the sum-of-cubes number 
and you're done, with no induction at all. Actually, induction was 
involved, since you need it to prove the two formulas that you used.

But the problem can be solved directly by induction as well, as
follows.

First check that it works for n=1.  1^2 = 1^3 - yup - that part's
okay.

Now assume it's true for n = k:

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

What is:

(1 + 2 + ... + k + (k+1))^2?

Let's look at it like this:

((1 + 2 + ... + k) + (k+1))^2,

which is (A+B)^2, if A = (1 + 2 + ... + k) and B is (k+1), right?

Well, (A + B)^2 = A^2 + 2AB + B^2,

so your sum is:

(1 + 2 + ... + k)^2 + 2(1 + 2 + ... + k)(k+1) + (k+1)^2     (1)

I assume you know that 1 + 2 + ... + k = k(k+1)/2, so (1) becomes:

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

By your induction hypotheses, the first term of (2) is just:

1^3 + 2^3 + ... + k^3

and so we just need to show that the rest of the junk on 
the right of (2) adds up to (k+1)^3.

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

QED.

-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/