Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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,

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/   
    
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/