Is My Proof by Induction Correct?

[zooxanthellae]

Homework Statement

Prove the formula by induction:

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

Homework Equations

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

The Attempt at a Solution

I started by showing that the formula holds for 1, since:

$$1^3 = (1)^2 = 1$$

Then I set about trying to prove that, if $$n$$ is true then $$n+1$$ is true as well, since this would prove the formula since we have our first validation of $$n$$ in the correct formula for $$1^3$$. Here goes:

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

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

Now I'll work with $$(1 + ... + n)^2 + (n + 1)^3$$, since that is equivalent to $$1^3 + ... + n^3 + (n + 1)^3$$.

I'm trying to prove, then, that $$(1 + ... + n)^2 + (n + 1)^3 = (1 + ... + n + n + 1)^2$$.

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

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

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

Next I used the relevant equation:

$$(n + 1)^3 = 2(n + 1)(n(n + 1)/2) + (n + 1)^2$$

Now it's just basic algebra:

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

$$(n + 1)(n+1)(n+1) = (n+1)(n^2 + n) + (n^2 + 2n + 1)$$

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

$$n^3 + 3n^2 + 3n + 1 = n^3 + 3n^2 + 3n + 1$$

Therefore:

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

Therefore:

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

So what is true for $$n$$ is true for $$n + 1$$ and the proof by induction seems to be complete. I just learned this method of proof, so critiques appreciated. Sorry for how long it is! I have a feeling it could be cleaned up more than a little bit.

Thanks.

 

[Mark44]

Homework Statement

Prove the formula by induction:

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

Homework Equations

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

The Attempt at a Solution

I started by showing that the formula holds for 1, since:

$$1^3 = (1)^2 = 1$$

Then I set about trying to prove that, if $$n$$ is true then $$n+1$$ is true as well, since this would prove the formula since we have our first validation of $$n$$ in the correct formula for $$1^3$$.

Something like "... if the statement is true for n, then it will be true for n + 1" is what you want to say. n is a number, not something that is true or false.

What you have is a sequence of statements P(1), P(2), ..., P(n), P(n + 1), ... You show that P(1) or some other base-case statement is true, then show that if P(n) is true, it necessarily follows that P(n + 1) is true as well.

Here goes:

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

OK, this is P(n).

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

And this is P(n + 1).

Now I'll work with $$(1 + ... + n)^2 + (n + 1)^3$$, since that is equivalent to $$1^3 + ... + n^3 + (n + 1)^3$$.

I'm trying to prove, then, that $$(1 + ... + n)^2 + (n + 1)^3 = (1 + ... + n + n + 1)^2$$.

Don't start off assuming what you want to show. Start with 1^3 + 2^3 + ... + n^3 + (n + 1)^on the left side and work with it until you reach (1 + 2 + ... + n + (n + 1))^2.

BTW, you can cut probably half or more of what you have below.

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

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

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

Next I used the relevant equation:

$$(n + 1)^3 = 2(n + 1)(n(n + 1)/2) + (n + 1)^2$$

Now it's just basic algebra:

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

$$(n + 1)(n+1)(n+1) = (n+1)(n^2 + n) + (n^2 + 2n + 1)$$

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

$$n^3 + 3n^2 + 3n + 1 = n^3 + 3n^2 + 3n + 1$$

Above, you have reached a statement that is identically true. If you can convince yourself and me that all of your steps are reversible operations, then you can conclude that the original equation must also be true.

A better way to do things, IMO, is to start with
$$(1 + ... + n)^2 + (n + 1)^3$$

and work with it to reach
$$(1 + ... + n + n + 1)^2$$

Therefore:

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

Therefore:

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

So what is true for $$n$$ is true for $$n + 1$$ and the proof by induction seems to be complete. I just learned this method of proof, so critiques appreciated. Sorry for how long it is! I have a feeling it could be cleaned up more than a little bit.

Thanks.

$$1^3 + 2^3 ... + n^3 + (n + 1)^3 = (1 + 2 + ... + n)^2 + (n + 1)^3 \text{By induction hypothesis}$$
$$= (\frac{n(n + 1)}{2})^2 + (n + 1)^3$$
$$= \frac{n^2(n + 1)^2}{4} + \frac{4(n + 1)^3}{4}$$
$$= \frac{(n + 1)^2(n^2 + 4n + 4)}{4} = \frac{(n + 1)^2(n + 2)^2}{4}$$
$$= (1 + 2 + ... + n + (n + 1))^2$$
Therefore (you should use this only once)
$$1^3 + 2^3 ... + n^3 + (n + 1)^3 = (1 + 2 + ... + n + (n + 1))^2$$

 

[zooxanthellae]

Something like "... if the statement is true for n, then it will be true for n + 1" is what you want to say. n is a number, not something that is true or false.

This was an error of expression on my part. I meant what you said (that " the statement is true for n".)

...Don't start off assuming what you want to show. Start with 1^3 + 2^3 + ... + n^3 + (n + 1)^on the left side and work with it until you reach (1 + 2 + ... + n + (n + 1))^2.

Again this is an error of expression on my part. By writing that, I was really trying to say something along the lines of "can we prove that this expression is true?" However, I will keep your point in mind in future problems, since I can see how what I wrote is actually wrong.

BTW, you can cut probably half or more of what you have below.
Above, you have reached a statement that is identically true. If you can convince yourself and me that all of your steps are reversible operations, then you can conclude that the original equation must also be true.

A better way to do things, IMO, is to start with
$$(1 + ... + n)^2 + (n + 1)^3$$

and work with it to reach
$$(1 + ... + n + n + 1)^2$$
...

Ah, I can see how your way accomplishes the same result in a much shorter time (and so, I guess, is a better proof). I suppose my long-winded proof is the way it is because I didn't stop to clean it up any (the proof is the thought process I went through).