3
$\begingroup$

I got a question in my homework, which is:

Find the following sum and prove your claim: $$1\cdot2 + 2\cdot3 + 3\cdot4 + \cdots + n\cdot(n+1).$$

I want to prove this by mathematical induction, but I couldn't find an expression of the sum. If anyone has any idea, please share with me. Thank you.

  • 0
    A cleaned up the question a little bit. I also don't think that this has much to do with Gauss sums, but I'm open to being proven wrong about this :)2012-02-05
  • 0
    What about $\sum_{k=1}^n k^2+k$?2012-02-05

5 Answers 5

8

$\bf Hint:$ $\sum_{i=1}^n i(i+1)=\sum_{i=1}^n i^2+\sum_{i=1}^n i$.

  • 1
    How do we evaluate $\sum_{i=1}^n i^2$? Doing this decomposition actually takes us a step backwards.2012-02-05
  • 2
    @Eric: It may be forwards in the event that Allan already knows the formula for $\sum i^2$.2012-02-05
6

Hint: Note that the general term in your series is $2\binom{n+1}{2}$.

From the definition of Pascal's Triangle, we get $$ \binom{n+2}{3}=\binom{n+1}{2}+\binom{n+1}{3} $$ which leads to the formula, ripe for telescoping series: $$ \binom{n+1}{2}=\binom{n+2}{3}-\binom{n+1}{3} $$

  • 2
    And, in general, we have that $$\sum_{k=1}^N \binom{n}{k} =\binom{n+1}{k+1}.$$ The so called "Hockey Stick" binomial formula.2012-02-05
  • 2
    @Eric: and that is a special case of $$\sum_k\binom{n-k}{i}\binom{k}{j}=\binom{n+1}{i+j+1}$$ (where $j=0$). I don't know if that has a name.2012-02-05
3

I see two approaches:

  1. You can decompose it into (1²+2²+...+n²) + (1+2+...+n). For both of them formulas expressing the sum directly are easily available.
  2. Since your terms are quadratic, the sum can be expressed by a polynomial of third degree.
    So you can use the ansatz a*x³ + b*x² + c*x + d and determine a, b, c, d so it fits 4 manually calculated elements.

You should be able to figure out the details from that. Both approaches work on other, similar problems too. So you should have them in your toolbox for later problems/the exam.

  • 0
    "You can use the ansatz"? Is this actually used in English? I'd be happy to hear that :)2012-02-05
  • 0
    @NiklasB. I hear it all the time in physics, even when talking in English. http://en.wikipedia.org/wiki/Ansatz2012-02-05
  • 0
    Nice :) Thanks!2012-02-05
  • 0
    @Niklas: "Ansatz" is now a perfectly serviceable (technical) English word. ;)2012-02-06
2

Another hint: $$k(k+1)=\frac{1}{3}(k(k+1)(k+2)-(k-1)k(k+1)).$$ The right-hand side gives you a telescoping sum.

  • 0
    See [robjohn's closely related answer](http://math.stackexchange.com/a/106055) using binomial coefficients.2012-02-05
0

If you don't know where to start, I suggest you rewrite the sum using the Σ(i:1-> n) notation. It eventually leads to a simpler expression.