Proof by Mathematical Induction

[gmmstr827]

Homework Statement

Prove: 1+2(2+3+4+···+n)+(n+1)=(n+1)²-1 for all n within N

Homework Equations

PMI

The Attempt at a Solution

I tried applying PMI starting with the basis step, allowing n=1, assuming the equation would be true. However 1+2(1)+(1+1)=?=(1+1)²-1 yields 5=?=3 which is false. The problem states that all n are within the natural numbers, which should include 1 (but not 0), but the equation suggests that 1 does not work [2(2+3+4+···+n) on the LHS starts with 2 instead of 1]. Is the statement false or can 1 not be used in the basis step for some reason? For n=2, the statement is true, but it should be true for all natural numbers.

 

[Mark44]

Homework Statement

Prove: 1+2(2+3+4+···+n)+(n+1)=(n+1)²-1 for all n within N

Homework Equations

PMI

The Attempt at a Solution

I tried applying PMI starting with the basis step, allowing n=1, assuming the equation would be true. However 1+2(1)+(1+1)=?=(1+1)²-1 yields 5=?=3 which is false. The problem states that all n are within the natural numbers, which should include 1 (but not 0), but the equation suggests that 1 does not work [2(2+3+4+···+n) on the LHS starts with 2 instead of 1]. Is the statement false or can 1 not be used in the basis step for some reason? For n=2, the statement is true, but it should be true for all natural numbers.

Your base step has to start with n = 2 or larger, since the numbers inside the parentheses on the left side start with 2 and go to n.

So if n = 2, you have 1 + 2(2) + 3 = (2 + 1)² - 1
On the left, the value is 8, the same as on the right.

 

[gmmstr827]

Your base step has to start with n = 2 or larger, since the numbers inside the parentheses on the left side start with 2 and go to n.

So if n = 2, you have 1 + 2(2) + 3 = (2 + 1)² - 1
On the left, the value is 8, the same as on the right.

That's what I was thinking. So since 1 is a natural number, and the problem states that the equation is true for all n in N-the set of natural numbers, should it be seen as 1 not being included in n, and therefore not being in N?

 

[Mark44]

Just prove that it's true for all natural numbers n, where n >= 2. The problem could have been worded to include this restriction, but that's a relatively minor detail, IMO.

 

[gb7nash]

I can see where the OP is coming from. The problem isn't worded correctly. It should say prove ... for n >= 2, (because what does (2 + ... + n) mean if n = 1?)

 

[Mark44]

Yes, I agree, the problem should have been worded more clearly. But assuming that the problem really means for n >= 2, can the OP continue from there?

 

[gmmstr827]

Yes, I agree, the problem should have been worded more clearly. But assuming that the problem really means for n >= 2, can the OP continue from there?

First, by using n=2 for the basis, I confirmed that the equation is true.
Then,
Assume true for n=k
1+2(2+3+4+···+k)+(k+1)=(k+1)²-1 for all k within N
Show true for n=k+1
1+2(2+3+4+···+k+k+1)+(k+1)+(k+1+1)=(k+1+1)²-1

I'm trying to contradict this somehow, and went through with it unsuccessfully as follows:
For sake of contradiction:
1+2(2+3+4+···+k+k+1)+(k+1)+(k+1+1)=/=(k+1+1)²-1
Subtract original (without the added 1):
1+2(2+3+4+···+k+k+1)+(k+1)+(k+1+1)-(1+2(2+3+4+···+k)+(k+1))=/=(k+1+1)²-1-((k+1)²-1)
Simplify:
2(k+1)+(k+1+1)=/=(k+1+1)²-(k+1)²
2(k+1)+(k+2)=/=(k+2)²-(k+1)²
2(k+1)+(k+2)=/=k²+4k+4-(k²+2k+1)
2k+2+k+2=/=2k+3
3k+4=/=2k+3

Which comes out to be true - I want it to be false for contradiction. In similar problems where instead of the equations being equal to each other, they were ≥ or ≤ to each other, and I would simply switch the direction and take out the "or equals to" line and do the same thing as above, but it would prove to be false, showing contradiction, and proving the original statement as true. Since this one is using an equals sign, is it possible to do it with this method? If I used a less than sign it would come out false, but I don't think that's appropriate, so I'll have to probably find a different method to use.

 

[gb7nash]

Assume true for n=k
1+2(2+3+4+···+k)+(k+1)=(k+1)²-1 for all k within N
Show true for n=k+1
1+2(2+3+4+···+k+k+1)+(k+1)+(k+1+1)=(k+1+1)²-1

I'm trying to contradict this somehow

No no no. Don't do this. You want to show

1+2(2+3+4+···+k+k+1)+(k+1+1)=(k+1+1)²-1

Make use of the inductive hypothesis, which is:

1+2(2+3+4+···+k)+(k+1)=(k+1)²-1

To start off, try manipulating the left side of the equation and arrive at the right side using the IH, so you start with:

1+2(2+3+4+···+k+k+1)+(k+1+1)= ...

 

[gmmstr827]

No no no. Don't do this. You want to show

1+2(2+3+4+···+k+k+1)+(k+1+1)=(k+1+1)²-1

Make use of the inductive hypothesis, which is:

1+2(2+3+4+···+k)+(k+1)=(k+1)²-1

To start off, try manipulating the left side of the equation and arrive at the right side using the IH, so you start with:

1+2(2+3+4+···+k+k+1)+(k+1+1)= ...

Would 2(2+3+4+···+k+k+1) = k(k+2)+k+1?
So it would all equal 1+k(k+2)+k+1+k+1+1
=k^2+4k+4

However, I need it to equal k^2+4k+3
Which I can get if I don't add an extra 1. So I use:
1+2(2+3+4+···+k+k+1)+(k+1)=(k+1+1)²-1
instead of
1+2(2+3+4+···+k+k+1)+(k+1+1)=(k+1+1)²-1

 

[gb7nash]

I don't really follow your logic. Start with:

1+2(2+3+4+···+k+k+1)+(k+1+1)

We want to manipulate it and make use of the IH to show that

1+2(2+3+4+···+k+k+1)+(k+1+1)=(k+1+1)²-1.

I'll get you started:

1+2(2+3+4+···+k+k+1)+(k+1+1)
= 1+2(2+3+4+···+k)+2(k+1)+(k+1)+1 (Do you see why this is true?)
= 1+2(2+3+4+···+k) + (k+1) + 2(k+1) + 1 (rearranging terms)
.
.
.
=(k+1+1)²-1

 

[gmmstr827]

The problem is that I have no idea where to find formulas to convert the expression 2(2+3+4+···+k) into a term. I know that I need to end up with k^2+4k+3 in order to show the RHS, but it seems like I'll be getting too many values. I've been looking through my book and trying to research it online but everything I find about the IH either skips that explanation or shows something with a summation which doesn't really explain it either. How do I go about changing it?
It seems like it would have to be k^2+k-2 which is equal to (k+2)(k-1) in order to be added within the remaining 1+k+1+2(k+1)+1 to equal k^2+4k+3 = k^2+4k+4-1=(k+2)^2-1 but how do I get to that?

 

[gb7nash]

I don't really follow your logic. Start with:

1+2(2+3+4+···+k+k+1)+(k+1+1)

We want to manipulate it and make use of the IH to show that

1+2(2+3+4+···+k+k+1)+(k+1+1)=(k+1+1)²-1.

I'll get you started:

1+2(2+3+4+···+k+k+1)+(k+1+1)
= 1+2(2+3+4+···+k)+2(k+1)+(k+1)+1 (Do you see why this is true?)
= 1+2(2+3+4+···+k) + (k+1) + 2(k+1) + 1 (rearranging terms)
.
.
.
=(k+1+1)²-1

The problem is that I have no idea where to find formulas to convert the expression 2(2+3+4+···+k) into a term.

Use the inductive hypothesis. Don't try to evaluate what 2(2+3+4+···+k) is. Look at what I bolded. What is that equal to due to the IH? (I really can't give you anymore than this or I'm practically handing you the answer. :tongue2:)

 

[gmmstr827]

Wait, you just substitute the part of the LHS that existed before adding +1 to both sides for the RHS before adding the +1? If so, this is so much less complicated that I thought. I was under the impression you had to do some kind of summation or use a formula to convert it into the values you need...

 

[gb7nash]

I was under the impression you had to do some kind of summation or use a formula to convert it into the values you need...

This is why the inductive hypothesis is so powerful. You don't have to sum the terms up. Just use the inductive hypothesis and you can convert the bolded terms to something else. Note that you can do this when performing a simple proof by induction. For this induction proof, we're assuming that the equation works for k (the inductive hypothesis that I listed above). You now want to show that it works for k+1.

So what comes next?

1+2(2+3+4+···+k+k+1)+(k+1+1)
= 1+2(2+3+4+···+k)+2(k+1)+(k+1)+1 (Do you see why this is true?)
= 1+2(2+3+4+···+k) + (k+1) + 2(k+1) + 1 (rearranging terms)
= ?

 

[gmmstr827]

1+2(2+3+4+···+k+k+1)+(k+1+1)
1+2(2+3+4+···+k)+2(k+1)+(k+1)+1
1+2(2+3+4+···+k)+(k+1)+2(k+1)+1
Recall: 1+2(2+3+4+···+k)+(k+1)=(k+1)²-1
(k+1)²-1+2k+2+1
k²+2k+1-1+2k+2+1
k²+4k+3
k²+4k+4-1
(k+2)(k+2)-1
(k+2)²-1
LHS=RHS
Therefore, 1+2(2+3+4+···+n)+(n+1)=(n+1)²-1 for all n within N.

 

[gb7nash]

You got it . Just don't forget to put equal signs between them.

 

[gmmstr827]

Yep. I just didn't realize how to change the expression until I looked at examples enough and finally noticed you simply substitute >.< Thanks for your help.