# Prove by induction $\sum_{i=0}^n i(i+1)(i+2) = (n(n+1)(n+2)(n+3))/4$

Anyone knows how to do this? I'm having trouble after the following step:

Prove by induction that $\sum_{i=0}^n i(i+1)(i+2) = (n(n+1)(n+2)(n+3))/4$

Thanks

$((n(n+1)(n+2)(n+3))/4) + (n+1)(n+2)(n+3)$

I'm not sure how to simplify it after this step.

Thanks

-
Factor (n+1)(n+2)(n+3). – Did May 26 '12 at 10:23
Here is a link to more general question: math.stackexchange.com/questions/219693/… – Martin Sleziak Jan 24 '14 at 12:50

If you notice that $$\frac{(n+1)(n+2)(n+3)(n+4)}4-\frac{n(n+1)(n+2)(n+3)}4=\frac{[(n+4)-n](n+1)(n+2)(n+3)}4=(n+1)(n+2)(n+3)$$ the inductive step should be easy.

This follows the idea which can be used in many similar proofs, namely that $$F(n)=\sum_{i=1}^n f(i) \Leftrightarrow F(n)-F(n-1)=f(n), F(0)=0.$$ See this answer by Bill Dubuque.

(I have used $F(n+1)-F(n)$ above, but this does not change too much, maybe you can try to work out $F(n)-F(n-1)$ yourself.)

In case you are already familiar with binomial coefficients, it might be interesting for you that if you divide this equation by six, you can rewrite it as $$\sum_{j=3}^{n+2}\binom j3=\binom{n+3}4,$$ which is a particular case of hockey-stick identity, see e.g. this question: induction proof concerning a sum of binomial coefficients

(This is not important for your induction proof, but it might be useful for you to notice connections between various areas you have learned. For instance, after rewriting the identity using binomial coefficients, you can also try to find a combinatorial interpretation.)

-
+1, I'm happy to see others promoting telescopy. – Bill Dubuque May 26 '12 at 16:03