Proving Induction: Solving Equations 1 and 2 with Expert Tips

[Jimmy84]

Homework Statement

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

Homework Equations

The Attempt at a Solution

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

Thanks.

 

[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.

 

[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)

 

[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

 

[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

 

[Jimmy84]

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

I couldn't 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 can't go further from that . because I can't take just n+1 as one single variable in order to make sense I need the other sum of real numbers of the equation.

 

[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)

 

[hgfalling]

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

 

[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

 

[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 I am 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 I am totally lost here I would appreciate some help.

 

[hgfalling]

Start by finding a closed formula for:

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

 

[Jimmy84]

Start by finding a closed formula for:

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

What do you mean by a closed formula?

 

[hgfalling]

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

 

[wisvuze]

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

I couldn't 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?

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".

 

[Jimmy84]

Start by finding a closed formula for:

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

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

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

 

[hgfalling]

In post #10, you wrote:

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

Now you have an expression you can fill in on the right side of that equation, right?

 

[Jimmy84]

In post #10, you wrote:


Now you have an expression you can fill in on the right side of that equation, right?

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


How can I start with the second problem?

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

 

[hgfalling]

Now use the result you just proved to substitute into the left and right sides of the second inequality.