# Stuck on proof by induction

• October 22nd 2010, 12:06 PM
Scorpy6
Stuck on proof by induction
Hello,
I start to solve this, but got stacked. Have no idea how to move on :confused:

Anybody help me ? (Thinking)

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) =>
• October 22nd 2010, 01:20 PM
emakarov
You are correct until the last line, which should be

1/2 [3k^2 + 7k + 6k + 10] = 1/2 (k+1) (3k+10)
• October 23rd 2010, 12:09 AM
Scorpy6
Can you give me some explanation about how you came to 6k+10 ? I really don't understand how that can be ...
• October 23rd 2010, 01:05 AM
tonio
Quote:

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

Tonio
• April 17th 2011, 11:08 AM
Scorpy6
Hello everybody :D I've got some trouble again with exercise like this one (Headbang) ..

Code:

http://twitpic.com/4m55bq
• April 17th 2011, 09:05 PM
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.

http://quicklatex.com/cache3/ql_8910...d9c6658_l3.png

Q.E.D.
• April 18th 2011, 04:45 AM
Scorpy6
Quote:

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.

http://quicklatex.com/cache3/ql_8910...d9c6658_l3.png

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 (Wink)
• April 18th 2011, 05:42 AM
You could also simplify to remove denominators as shown in the attachment.
• October 19th 2011, 05:01 AM
Scorpy6
Re: Stuck on proof by induction
Hello everybody, again me :D

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? (Worried)
Thanks
• October 19th 2011, 05:10 AM
emakarov
Re: Stuck on proof by induction
I think it should be (2k^3+9k^2+13k+6) / 6.
• October 19th 2011, 05:25 AM
Scorpy6
Re: Stuck on proof by induction
One mistake and everything is screwed up :D But it's great when there is someone that can fix that :) Thanks a lot, I solve it
• October 19th 2011, 05:59 AM
Prove It
Re: Stuck on proof by induction
Quote:

Originally Posted by Scorpy6
Hello everybody, again me :D

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? (Worried)
Thanks

Base Step: $\displaystyle n = 1$

\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 n = k$, so assume $\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 n = k + 1$, i.e. show that $\displaystyle 1^2 + 2^2 + 3^2 + \dots + k^2 + (k + 1)^2 = \frac{(k+1)(k + 2)(2k + 3)}{6}$.

\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. :)
• October 19th 2011, 07:16 AM
Re: Stuck on proof by induction
Or...

Show that

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

if

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

Then

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

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

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

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