Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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 at 12:50

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
1  
+1, I'm happy to see others promoting telescopy. –  Bill Dubuque May 26 '12 at 16:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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