# Stuck on proof by induction

• Oct 22nd 2010, 01: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) =>
• Oct 22nd 2010, 02: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)
• Oct 23rd 2010, 01: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 ...
• Oct 23rd 2010, 02: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
• Apr 17th 2011, 12:08 PM
Scorpy6
Hello everybody :D I've got some trouble again with exercise like this one (Headbang) ..

Code:

http://twitpic.com/4m55bq
• Apr 17th 2011, 10: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.
• Apr 18th 2011, 05: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)
• Apr 18th 2011, 06:42 AM
You could also simplify to remove denominators as shown in the attachment.
• Oct 19th 2011, 06: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
• Oct 19th 2011, 06:10 AM
emakarov
Re: Stuck on proof by induction
I think it should be (2k^3+9k^2+13k+6) / 6.
• Oct 19th 2011, 06: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
• Oct 19th 2011, 06: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. :)
• Oct 19th 2011, 08: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\;\;\;?$