1. ## Proof by induction

My discreet class is working on a project and we are having trouble proving the following equation. We are to prove it using induction:

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

We are unsure what the base case is even supposed to be. Would it be a base case of 1 or not? The multiplication factor on left side of the equation is confusing us.

2. Originally Posted by baker11108
My discreet class is working on a project and we are having trouble proving the following equation. We are to prove it using induction:

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

We are unsure what the base case is even supposed to be. Would it be a base case of 1 or not? The multiplication factor on left side of the equation is confusing us.
Can you double-check the question to verify whether it should be something like

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

If this is the case, then the minimum value n can be within the brackets is 2,
since the value 3 tells you that the numbers being summed in brackets are
all increasing by 1.

So your base case ought to be n=2.

To prove this using induction

P(k) is

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

P(k+1) is

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

Try to express P(k+1) in terms of P(k) to show that P(k+1) must be true if P(k) is

3. No, I have it as what I originally posted.

4. If you substitute some value of n into both sides,
you will see the sides are not equal.

For example, if n=5

$1+2(2+3+4+5)+(5-1)=1+2(14)+4=33$

$(5+1)^2-1=6^2-1=36-1=35$

They differ by 2

However, if you replace the n-1 with n+1, they are then equal.

Hence, in sticking with the original formula,
there is no point using induction to prove it's not true.

However you can use induction to prove that the following is true

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

5. Okay so let's assume it is n+1 on the left side rather n-1:

we get:

2(2+3+...+[k+1])+k+3=(k+2)^2-1

k+3+(k+1)^2-1

k^2+3k+3 doesn't equal the right side of the equation which is k^2+2k + 3.

I need another K to make the sides equal. Where am I going wrong?

6. Originally Posted by baker11108
Okay so let's assume it is n+1 on the left side rather n-1:

we get:

2(2+3+...+[k+1])+k+3=(k+2)^2-1

k+3+(k+1)^2-1

k^2+3k+3 doesn't equal the right side of the equation which is k^2+2k + 3.

I need another K to make the sides equal. Where am I going wrong?
You have a couple of errors there...

You added 2 to k+1 and neglected the extra k+1 inside the brackets of the LHS.

You should have

P(k)

$1+2(2+3+...+k)+(k+1)=(k+1)^2-1$ ?

P(k+1)

$1+2(2+3+....+k+[k+1])+(k+2)=(k+2)^2-1$ ?

Now find the P(k) expression in that

$\color{blue}1+2(2+3+...+k)\color{black}+2(k+1)\col or{blue}+(k+1)\color{black}+1=(k+2)^2-1$ ?

Now use your RHS from P(k) to evaluate the LHS in the above line

$(k+1)^2-1+2(k+1)+1=k^2+2k+1-1+2k+2+1=k^2+4k+3$

which is

$(k+2)^2-1$

Hence if P(k) is true, it causes P(k+1) to be true