Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

(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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search