Induction Proof: sum[k=1,n][k(k+1)] = [n(n+1)(n+2)]/3

I

ifoan

New member
Joined
Oct 19, 2006
Messages
36
Prove that, for each positive integer n,

\(\displaystyle \sum_{k=1}^{n}\, k(k\, +\, 1)\, =\, \frac{n(n\, +\, 1)(n\, +2\, )}{3}\)


So I try for n = 1:

\(\displaystyle 1(1\, +\, 1)\, =\, \frac{1(1\, +\, 1)(1\, +\, 2)}{3}\)

\(\displaystyle 2\, =\, \frac{1x2x3}{3}\)

\(\displaystyle 2\, =\, \frac{6}{3}\)

\(\displaystyle 2\, =\, 2\)

Now, assume it is true for n:

\(\displaystyle \sum_{k=1}^{n}\, =\, \frac{n(n\, +\, 1)(n\, +\, 2)}{3}\)

Prove it is also true for n+1:

\(\displaystyle \sum_{k=1}^{n+1}\, =\, \frac{n(n\, +\, 1)(n\, +\, 2)}{3}\, +\, (n\, +\, 1)\)

\(\displaystyle \sum_{k=1}^{n+1}\, =\, \frac{n(n\, +\, 1)(n\, +\, 2)\, +\, 3(n\, +\, 1)}{3}\)

\(\displaystyle \sum_{k=1}^{n+1}\, =\, \frac{n(n^{2}\, +\, 3n\, +\, 2)\, +\, 3n\, +\, 3}{3}\)

\(\displaystyle \sum_{k=1}^{n+1}\, =\, \frac{n^{3}\, +\, 3n^{2}\, +\, 2n\, +\, 3n\, +\, 3}{3}\)

\(\displaystyle \sum_{k=1}^{n+1}\, =\, \frac{n^{3}\, +\, 3n^{2}\, +\, 5n\, +\, 3}{3}\)

\(\displaystyle \sum_{k=1}^{n+1}\, =\, \frac{n(n^{2}\, +\, 3n\, +\, 5) \, +\, 3} {3}\)

\(\displaystyle \sum_{k=1}^{n+1}\, =\, \frac{n(n\, +\, 2)(n\, +\, 3)\, +\, 3}{3}\)

I'm trying to figure out what im doing wrong, can anyone help me out?

thanks!
 
seems like the tex codes are a little different here.

n+1 and n are on top of sigma
and k=1 is on the bottome of sigma
 
Re: Induction Proof

ifoan said:
Prove that, for each positive integer n,

\(\displaystyle \sum_{k=1}^{n}k(k+1)=\frac{n(n+1)(n+2)}{3}\)


So I try for n=1:
\(\displaystyle (1(1+1))=\frac{1(1+1)(1+2)}{3}\)

\(\displaystyle 2=\frac{1x2x3}{3}\)

\(\displaystyle 2=\frac{6}{3}\)

\(\displaystyle 2=2\)

Now, assume it is true for n:
\(\displaystyle \sum_{k=1}^{n}=\frac{n(n+1)(n+2)}{3}\)

Prove it is also true for n+1:
\(\displaystyle \L\\\sum_{k=1}^{n+1}=\frac{n(n+1)(n+2)}{3}+\underbrace{(n+1)}_{\text{right here}}\)

Add \(\displaystyle (n+1)(n+2)\) instead of \(\displaystyle n+1\). You will

find, after doing the algebra and induction, you will wind up with \(\displaystyle \L\\\frac{(n+1)(n+2)(n+3)}{3}\). Which proves by induction. Make

sure you write QED. It looks erudite. :D

\(\displaystyle \sum_{k=1}^{n+1}=\frac{n(n+1)(n+2)+3(n+1)}{3}\)

\(\displaystyle \sum_{k=1}^{n+1}=\frac{n(n^{2}+3n+2)+3n+3}{3}\)

\(\displaystyle \sum_{k=1}^{n+1}=\frac{n^{3}+3n^{2}+2n+3n+3}{3}\)

\(\displaystyle \sum_{k=1}^{n+1}=\frac{n^{3}+3n^{2}+5n+3}{3}\)

\(\displaystyle \sum_{k=1}^{n+1}=\frac{n(n^{2}+3n+5) + 3} {3}\)

\(\displaystyle \sum_{k=1}^{n+1}=\frac{n(n+2)(n+3)+3}{3}\)

I'm trying to figure out what im doing wrong, can anyone help me out?

thanks!
Click to expand...
 
ok, disregard that last thing

then we got:

\(\displaystyle \frac{n(n+1)(n+2)+3(n+1)(n+2)}{3}\)

\(\displaystyle \frac{n(n^{2}+3n+2)+3(n^{2}+3n+2)}{3}\)

\(\displaystyle \frac{n^{3}+3n^{2}+2n+3n^{2}+9n+6}{3}\)

\(\displaystyle \frac{n^{3}+6n^{2}+11n+6}{3}\)

\(\displaystyle \frac{n(n^{2}+6n+11)+6}{3}\)

and im stuck..
did i do something wrong? im a beginner at induction
 
ifoan said:
can i ask why we add (x+1)(x+2) and not just (x+1)?
Click to expand...

Because of the induction step. You have k(k+1)

You showed step 1 already.

Step 2, the induction step:

\(\displaystyle \L\\1\cdot{2}+2\cdot{3}+3\cdot{4}+.........+k(k+1)=\frac{k(k+1)(k+2)}{3}\)

Now, to show \(\displaystyle P_{k+1}\) is true:

\(\displaystyle \L\\1\cdot{2}+2\cdot{3}+3\cdot{4}+........+(k+1)(k+2)=\frac{(n+1)(n+2)(n+3)}{3}\)

Rewrite the left side and use the induction hypothesis as follows:

\(\displaystyle \L\\1\cdot{2}+2\cdot{3}+3\cdot{4}+......+k(k+1)+(k+1)(k+2)=\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=\frac{(k+1)(k+2)(k+3)}{3}\)

QED
 
thank you galactus.

I know that it is going to work, but my algebra skills are rusty.

im trying to figure out the steps from:
\(\displaystyle \frac{k(k+1)(k+2)}{3}+(k+1)(k+2)\)

to

\(\displaystyle \frac{(k+1)(k+2)(k+3)}{3}\)
 
Remember your factoring?.

It's easy.

\(\displaystyle \L\\\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)\)

=\(\displaystyle \L\\\frac{\fbox{k}(k+1)(k+2)+\fbox{3}(k+1)(k+2)}{3}\)
........\(\displaystyle \nwarrow{}\)............\(\displaystyle \nearrow{}\)

See the k+3 there?. Factor.

=\(\displaystyle \L\\\frac{(k+1)(k+2)(k+3)}{3}\)
 
galactus, im sorry but i don't see the k+3.

im cofused. would i go from:

=\(\displaystyle \L\\\frac{k(k+1)(k+2)+3(k+1)(k+2)}{3}\)

to

=\(\displaystyle \L\\\frac{n(n^{2}+3n+2)+3(n^{2}+3n+2)}{3}\)

then

=\(\displaystyle \L\\\frac{n^{3}+3n^{2}+2n+3n^{2}+9n+6}{3}\)?
 
Hello, ifoan!


You have: \(\displaystyle \L \,\frac{k\overbrace{(k+1)(k+2)}^{\nwarrow\;}\,+\,3\overbrace{(k+1)(k+2)}^{\nwarrow\;}}{3}\)

Do you see the common factors? . . . Factor them out!

. . \(\displaystyle \L\frac{\overbrace{(k+1)(k+2)}^{\;\swarrow}\, (k\,+\,3)}{3}\)

 
oh ok, i think i get it.

we are throwing out one of the (k+1)(k+2) and we have k(k+1)(k+2)+3.

so its really (k+1)(k+2)(k+3)

?
 
ifoan said:
oh ok, i think i get it.

we are throwing out one of the (k+1)(k+2) and we have k(k+1)(k+2)+3.Errrr.....no. We aren't throwing out ANYTHING

so its really (k+1)(k+2)(k+3)

?
Click to expand...

A basic factoring review. When you have an expression like

ac + bc

where there is a common factor in each term, you pull out the common factor to the front of a set of parentheses, and put what is left from each term inside the parentheses:

c(a + b)

Compare this to your expression:

k(k + 1)(k + 2) + 3(k + 1)(k + 2)

The two terms have a common factor, which is (k + 1)(k + 2)

Pull that common factor out in front of a set of parentheses, and put what is left from each term INSIDE the parentheses:

(k + 1)(k + 2)(k + 3)

See?
 
You must log in or register to reply here.
Top