Guide to Constructing a Proof by Induction for Natural Numbers

[wubie]

Hello,

I have to prove the following by induction for all of n which are elements of N:

1^3 + 2^3 + ... n^3 = 1/4 * n^2 * (n + 1)^2

Now, I have never been successful at proofs, much less proofs by induction. And I never have really had any formal instruction on how to construct a proof by induction. So I could use all the help I can get.

NOTE: I do NOT want someone to give me an answer. I would rather someone guide me to an answer illustrating a formal method of constructing a proof by induction (with anotations on the side if possible). [?]

BTW, I am using "Schaum's Outlines: Modern Abstract Algebra". And my question is in Chapter 3: Natural Numbers, page 37, 25 c).

I know this is a tall order, but if anyone cares to spend the time to teach, I will most certainly spend the time to learn.

Here is my work so far. Note: Although I may have some steps in the proper order, and it may seem like I know what I am doing, I really do not. That is, I don't know the reasoning behind every step that I do and why it is in the format that it is. That being said, onto the proof.


Propostition:

== state the proposition

P(n): 1^3 + 2^3 + ... n^3 = 1/4 * n^2 * (n + 1)^2

for every n which is an element of N (the set of Natural numbers).


Base Case: P(1)

== show that the proposition holds for the first element in the set.

1^3 = 1/4 * 1^2 * (1 + 1)^2
1 = 1

So P(1) is true.


Inductive Case:

== show that if the proposition holds for an element k, it should hold for it's successor.

If P(k) is true then P(k+1) must be also true.

(Here is where I am definitely in the dark on how to proceed).


Any help is appreciated. BTW, how is the proof so far? Am I interpreting it correctly? And is my format sound?

 

[quantumdude]

Oooh, I love these!

Let me start from scratch.

Proof by Induction
For some statement P(n) on some integer n, if it is the case that:

1. P(1) is true and
2. P(k)-->P(k+1),

for some integer k, then it is the case the P(n) is true for all n.

The statement P(n) in your case is that:

edit: After the summation sign (Σ), the subscript (j=1) gives the lower limit of summation, and the superscript (n) gives the upper limit of summation. Sorry, I can't make it look any prettier than that.

Σ_j=1ⁿj³=(1/4)n²(n+1)²

You've shown that P(1) is true. For the inductive step, write down P(k+1) and try to extract P(k) from it.

P(k+1)=Σ_j=1^k+1j³=(1/4)(k+1)²(k+2)²

Note that all I did is substitute k+1 for n wherever n appears in P(n). Now, note that I can rewrite the sum above as a sum from 1 to k, plus the (k+1)^st term, as follows:

Σ_j=1^kj³+(k+1)³=(1/4)(k+1)²(k+2)²

Now note that the sum from 1 to k is just P(k). Assuming P(k) is true, you can cancel it from the left hand side if you also cancel the right side of P(k) from the right side of P(k+1). You should be left with an identity, which proves that P(k) implies P(k+1).

edit: just worked it out and it comes out perfect

 

[wubie]

Ok. I did what you did Tom all the way up to the point where I sub into P(n) k+1 for every n in P(n). But it is the extraction of P(k) which gives me trouble.

BTW, the phrasing "extract P(K)" was perfect. That was a part I didn't originally understand with respect to induction. But you rectified that.

I see this part:

Now note that the sum from 1 to k is just P(k).

But I can seem to get this part:

Assuming P(k) is true, you can cancel it from the left hand side if you also cancel the right side of P(k) from the right side of P(k+1). You should be left with an identity, which proves that P(k) implies P(k+1).

[?]

 

[quantumdude]

But I can seem to get this part:

Assuming P(k) is true, you can cancel it from the left hand side if you also cancel the right side of P(k) from the right side of P(k+1). You should be left with an identity, which proves that P(k) implies P(k+1).

OK, note that the part in blue below is just P(k).

Σ_j=1^kj³+(k+1)³=(1/4)(k+1)²(k+2)²

What you need to do is expand the right hand side of both P(k) and of P(k+1). Then, you can subtract Σ_j=1^kj³ from the left side of the above, and you can also subtract (1/4)x²(x+1)² from the right side of the above (since those two quantities are equal).

What you will be left with is:

(k+1)³=(1/4)(4k³+12k²+12k+4)

or...

(k+1)³=k³+3k²+3k+1,

which is an identity.

edit: fixed an omission

 

[wubie]

Geez Tom, I must be the most dense substance on the planet. I can see what you are doing the left side of the equation. But I just can't see what you are doing on the right side. I also understand what you are saying. I just cannot see it.

[?]

I see this and worked out this relation:

[sum]_i=1ⁿi³=(1/4)(n²)(n+1)²

and I see and worked out this part of the next relation on the left side myself:

[sum]_i=1^ki³ + (k+1)³

But I don't see how you arrived at

(1/4)(k+1)³(k+1+1)³

on the left side.


This is what I would have at if I was to do it:

(1/4)(k+1)²(k+1+1)²

How did you get a power of three? I can't see that. [?]

If I was to do it this way:

{ (1/4)(k²)(k+1)² } + (k+1)³

I still don't see how I would get

(1/4)(k+1)³(k+1+1)³


What the hey??!?? [?]


Am I missing some basic algebraic step? [?]


At least I understand what you are trying to do. I just don't understand how you arrived at the answer.

 

[quantumdude]

OK, here is the solution in all the gory details.

P(k)=Σ_j=1^k=(1/4)k²(k+1)²

Expanding the rightmost side, I get:

P(k)=Σ_j=1³=(1/4)(k⁴+2k³+k²)

Now, look at P(k+1):

Σ_j=1^k+1j³=(1/4)(k+1)²(k+2)²

I am going to manipulate both sides of this statement, one at a time:

Isolate (k+1)^st Term On Left Side:
Σ_j=1^k+1=Σ_j^kj³+(k+1)³

Expand Right Side:
(1/4)(k⁴+6k³+13k²+12k+4)

So, I have:

Σ_j=1^kj³+(k+1)³=(1/4)(k⁴+6k³+13k²+12k+4)

Now, remember P(k)? Assume it is true, and subtract it from P(k+1). It will be handy if you subtract the left side of P(k) from the left side of P(k+1), and do likewise with their right sides. I am going to denote both sides of P(k) with the color blue.

Then you get:

Σ_j=1^kj³+(k+1)³-Σ_j=1^kj³=(1/4)(k⁴+6k³+13k²+12k+4)-(1/4)(k⁴+2k³+k²)

And finally,

(k+1)³=k³+3k²+3k+1

which is an identity. Therefore, P(k)-->P(k+1).

edit: fixed superscript bracket

 

[quantumdude]

Originally posted by wubie
But I don't see how you arrived at

(1/4)(k+1)³(k+1+1)³

on the left side.

You mean the right side, don't you?

Ah, see, that's a sophisticated mathematical technique known as a "mistake".

Sorry, I've fixed the error. It should read as you have it below:

This is what I would have at if I was to do it:

(1/4)(k+1)²(k+1+1)²

Yes, that's it. Proceed from there.

 

[wubie]

Alright. I thought I was going insane there for a minute.

I have been known to make some pretty weird mathematical assumptions. (You know your assumptions are weird when the prof. looks at you with that look, "What the heck are you doing in my class?" It sure shakes one's confidence in one's mathematical abilities).

Oh, by the way, for future reference, I do not know my right from my left.

Ok. I will see if I can get the proof without looking at your solution. I don't like copying. I like doing. I just need a little help implementing it.

Thanks for your help Tom.

Especially for the comment about extractin P(k). That comment sort of crystalized things for me.