# Thread: Stuck on proof by induction

1. ## Stuck on proof by induction

Hello,
I start to solve this, but got stacked. Have no idea how to move on

Anybody help me ?

Code:
5+8+11+…+ (3n+2) = 1/2n(3n+7)
n=1
5+8+11+…+ (3*1+2) = 1/2 *1 (3*1+7) => 5=5

n=k
5+8+11+…+ (3k+2) = 1/2 k(3k+7)

n=k+1

5+8+11+…+ (3(k+1)+2) = 1/2(k+1) (3(k+1)+7)

5+8+11+…+ (3k+5) = 1/2  (k+1) (3k+10)

5+8+11+…+ (3k+2) + (3k+5) = 1/2 (k+1) (3k+10)

1/2 k(3k+7) + (3k+5) =  1/2 (k+1) (3k+10)

1/2 [3k^2 + 10k + 5] = 1/2 (k+1) (3k+10)

=>

2. You are correct until the last line, which should be

1/2 [3k^2 + 7k + 6k + 10] = 1/2 (k+1) (3k+10)

3. Can you give me some explanation about how you came to 6k+10 ? I really don't understand how that can be ...

4. Originally Posted by Scorpy6
Can you give me some explanation about how you came to 6k+10 ? I really don't understand how that can be ...

The $\displaystyle \frac{1}{2}$ in the LHS of the line before the last one only applies to $\displaystyle k(3k+7)=3k^2+7k$ , so if you want to keep it instead of $\displaystyle 3k+5$ you must put $\displaystyle 6k+10$...

Tonio

5. Hello everybody I've got some trouble again with exercise like this one ..

Code:
http://twitpic.com/4m55bq

6. 1. Where is your base step?

2. For your inductive step, you need to work on the LHS and show that you get the RHS, you can't keep bringing down the desired RHS.

Q.E.D.

7. Originally Posted by Prove It
1. Where is your base step?

2. For your inductive step, you need to work on the LHS and show that you get the RHS, you can't keep bringing down the desired RHS.

Q.E.D.
1. I did not mention the base step here.
2. Guess that you did not understand me... I was working on the LHS untill I got k(k+3)(k+3)+4/4(k+1)(k+2)(k+3).... So the problem was that i didn't know how to transform k(k+3)(k+3)+4 to (k+1)(k+4), like on the RHS.
But after consultations with the professor, I've learn that
Thanks anyway

8. You could also simplify to remove denominators as shown in the attachment.

9. ## Re: Stuck on proof by induction

Hello everybody, again me

Now i'm trying to solve or prove this one:

1^2+2^2+3^2+....+n^2=n(n+1)(2n+1)/6

And I came to the third step where i got this one:

2k^3+10k^2+13k+6 on the LHS. I know that to solve this and get the same like on RHS, I need to work with division with polynoms, but even if i try to do that, still can't prove LHS=RHS.

Can anybody help me somehow?
Thanks

10. ## Re: Stuck on proof by induction

I think it should be (2k^3+9k^2+13k+6) / 6.

11. ## Re: Stuck on proof by induction

One mistake and everything is screwed up But it's great when there is someone that can fix that Thanks a lot, I solve it

12. ## Re: Stuck on proof by induction

Originally Posted by Scorpy6
Hello everybody, again me

Now i'm trying to solve or prove this one:

1^2+2^2+3^2+....+n^2=n(n+1)(2n+1)/6

And I came to the third step where i got this one:

2k^3+10k^2+13k+6 on the LHS. I know that to solve this and get the same like on RHS, I need to work with division with polynoms, but even if i try to do that, still can't prove LHS=RHS.

Can anybody help me somehow?
Thanks
Base Step: $\displaystyle \displaystyle n = 1$

\displaystyle \displaystyle \begin{align*} LHS &= 1^2 \\ \\ RHS &= \frac{1(1 + 1)(2\cdot 1 + 1)}{6} \\ &= \frac{1 \cdot 2 \cdot 3}{6} \\ &= 1 \\ &= LHS \end{align*}

Inductive Step: Assume the statement is true for $\displaystyle \displaystyle n = k$, so assume $\displaystyle \displaystyle 1^2 + 2^2 + 3^2 + \dots + k^2 = \frac{k(k+1)(2k+1)}{6}$.

Now we need to prove the statement is true for $\displaystyle \displaystyle n = k + 1$, i.e. show that $\displaystyle \displaystyle 1^2 + 2^2 + 3^2 + \dots + k^2 + (k + 1)^2 = \frac{(k+1)(k + 2)(2k + 3)}{6}$.

\displaystyle \displaystyle \begin{align*} LHS &= 1^2 + 2^2 + 3^2 + \dots + k^2 + (k + 1)^2 \\ &= \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 \\ &= \frac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6} \\ &= \frac{(k + 1)\left[k(2k + 1) + 6(k + 1)\right]}{6} \\ &= \frac{(k + 1)(2k^2 + k + 6k + 6)}{6} \\ &= \frac{(k + 1)(2k^2 + 7k + 6)}{6} \\ &= \frac{(k+1)(2k^2 + 4k + 3k + 6)}{6} \\ &= \frac{(k + 1)[2k(k + 2) + 3(k + 2)]}{6} \\ &= \frac{(k + 1)(k + 2)(2k + 3)}{6} \\ &= RHS \end{align*}

Q.E.D.

13. ## Re: Stuck on proof by induction

Or...

Show that

$\displaystyle 1^2+2^2+....+k^2+(k+1)^2=\frac{(k+1)(k+2)(2k+3)}{6 }$

if

$\displaystyle 1^2+2^2+...+k^2=\frac{k(k+1)(2k+1)}{6}$

Then

$\displaystyle \frac{k(k+1)(2k+1)}{6}+\frac{6(k+1)^2}{6}=\frac{(k +1)(k+2)(2k+3)}{6}\;\;\;?$

$\displaystyle [k+1][k(2k+1)+6(k+1)]=[k+1][(2k+3)(k+2)]\;\;\;?$

$\displaystyle k(2k+1)+6(k+1)=(2k+3)(k+2)\;\;\;?$

$\displaystyle 2k^2+k+6k+6=2k^2+4k+3k+6\;\;\;?$