# Prove using induction

1. Apr 25, 2010

### Jimmy84

1. The problem statement, all variables and given/known data
Prove using induction

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

2.) 1^3 + 2^3 + ... + (n-1)^3 < (n^4)/4 < 1^3 + 2^3 + ... + n^2

2. Relevant equations

3. The attempt at a solution

I dont have a clue about how to start to do the problems can anyone help me ?

Thanks.

2. Apr 25, 2010

### hgfalling

When you don't know what to do, start by writing down what you know.

How to prove a theorem by induction.

1) Prove a case (usually n=1 or something).
2) Prove that if your theorem is true for some value of n, it is true for n+1.

So start by proving the statements for n=1, or maybe n=3 since the second statement involves n-1.

Then prove that IF it's true for n, it's true for n+1.

3. Apr 25, 2010

### lanedance

do you understand the inductive process?

First show its true for a particular n, usually n=1
Then asumes it true for n, see if you can show it is then true for n+1 based on that fact

Then it is true for all n greater than 1 (or whatever value you started at)

4. Apr 25, 2010

### wisvuze

I've done the first question before, it isn't that easy (unless you look it up what I'm going to post below).
It's related to these numbers (n^3) : (cubic numbers)
1^2 = 1
2^3 = 8 = 3 + 5
3^3 = 7 + 8 + 9
4^3 = 11 + 13 + 15 + 17
.. et c
generalize and these results and prove the generalization, then you may use it for 1^3 + ... + n^3 = (1+2+..+n)^2.

this may help you: 1 + 3 + ... + 2(n) - 1 = n^2
good luck

5. Apr 26, 2010

### lanedance

as i think wisvuze is implying you may need to use a few inductions (rather than just the single inductive step) to get the result - have a try & we'll step through it

6. Apr 26, 2010

### Jimmy84

Im familiar with having a single inductive step however the ones that use more step are more complicated.

I couldnt find a generalization for
1^2 = 1
2^3 = 8 = 3 + 5
3^3 = 7 + 8 + 9
4^3 = 11 + 13 + 15 + 17

There is no generalization I could find for 1, 8, 24, and 56. what can I do about it?

In problem one

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

would then be

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

but I cant go further from that . because I cant take just n+1 as one single variable in order to make sense I need the other sum of real numbers of the equation.

7. Apr 26, 2010

### lanedance

ok so examining n+1 case gives (note i've just added tex tags around you formula - try clicking on equation to see what i mean):
$$1^3 + 2^3 + 3^3 + ... + n^3 + (n+1)^3 = (1 + 2 + 3 + ... +n+ (n+1))^2$$

exapanding some of the square
$$(1^3 + 2^3 + 3^3 + ... + n^3) + (n+1)^3 = ((1 + 2 + 3 + ... +n) +(n+1))^2$$
$$(1^3 + 2^3 + 3^3 + ... + n^3) + (n+1)^3 = (1 + 2 + 3 + ... +n)^2 +2(n+1)(1 + 2 + 3 + ... +n) + (n+1)^2$$

now if we assume the orginal hypothesis is true for n, it reduces to:
$$(n+1)^3 = 2(n+1)(1 + 2 + 3 + ... +n) + (n+1)^2$$

removing a factor of (n+1)
$$(n+1)^2 = 2(1 + 2 + 3 + ... +n) + (n+1)$$

if you can prove the above relation you're pretty much there - so you could try induction again (i haven't done it, but looks like a reasonable way to attempt the problem)

Last edited: Apr 27, 2010
8. Apr 26, 2010

### hgfalling

This last relation follows directly from the formula for summing the first n integers.

9. Apr 27, 2010

### lanedance

cool, then induction should work for that if you can't just assume it & then you just need to show the hypthesis is true for some starting n value

10. May 15, 2010

### Jimmy84

Sorry I have been very busy all this time it has been quite hard to find a way to solve this problem.

You told me to prove
$$(n+1)^2 = 2(1 + 2 + 3 + ... +n) + (n+1)$$
but im not sure about how to do that.

I tried $$(n+2)^2 = 2(1 + 2 + 3 + ... +n+1) + (n+2)$$
then $$n^2 +4n +4 = 2 (1+2+3+... +n+1) + (n+2)$$

But im totally lost here I would appreciate some help.

11. May 15, 2010

### hgfalling

Start by finding a closed formula for:

$$\sum_{k=1}^n k = (1 + 2 + 3 + ... + (n-1) + n)$$

12. May 15, 2010

### Jimmy84

What do you mean by a closed formula?

13. May 15, 2010

### hgfalling

Something that's only in terms of n, and doesn't involve a summation.

14. May 15, 2010

### wisvuze

Notice: 1^2 = 1, 2^3 = 3 + 5 .. et c nth term is the sum of n odd numbers, starting from where n-1's odd terms left off

This question was presented this way in Donald Knuth's popular book "The Art of Computer Programming".

15. May 16, 2010

### Jimmy84

$$n(n+1)/2$$

What use I can give to that in order to prove the original equation?

16. May 16, 2010

### hgfalling

In post #10, you wrote:
Now you have an expression you can fill in on the right side of that equation, right?

17. May 17, 2010

### Jimmy84

ok $$(n+1)^2 = n(n+1) + (n+1)$$
that is $$n^2+2n+1 = n^2+2n+1$$

2.) $$1^3 + 2^3 + ... + (n-1)^3 < (n^4)/4$$