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$


$((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.



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: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$

(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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.