# Find the Sum $1\cdot2+2\cdot3+\cdots + (n-1)\cdot n$

Find the sum $$1\cdot2 + 2\cdot3 + \cdot \cdot \cdot + (n-1)\cdot n.$$

This is related to the binomial theorem. My guess is we use the combination formula . . .

$C(n, k) = n!/k!\cdot(n-k)!$

so . . . for the first term $2 = C(2,1) = 2/1!(2-1)! = 2$

but I can't figure out the second term $3 \cdot 2 = 6$ . . .

$C(3,2) = 3$ and $C(3,1) = 3$ I can't get it to be 6.

Right now i have something like . . . $$C(2,1) + C(3,2) + \cdot \cdot \cdot + C(n, n-1)$$ The 2nd term doesn't seem to equal 6.

What should I do?

• Is it required to use the binomial theorem? – Alraxite Apr 20 '13 at 23:14
• @Alraxite Question says Find the Sum, but example in the book uses C(n,k) to solve it (and end up with something like (n+1)n/2 to the sum in the example). I dont think you need to though. – rbtLong Apr 20 '13 at 23:17

This doesn't solve it using the binomial theorem, but this is one way to do it:

The general term is given by $a_n =n(n+1) = n^2 + n$.

So the sum to $n$ terms: $$\sum_{i=1}^{n} a_i = \sum_{i=1}^{n} i^2 + \sum_{i=1}^{n} i$$ As you probably may know,

$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

• sorry i had the question written wrong, it is suposed to be (n-1)n – rbtLong Apr 20 '13 at 23:52
• @rbtLong Then the series is $0\cdot1 + 1\cdot2 + 2\cdot3 + \cdot\cdot\cdot + (n-1)n$. This is basically the same series but with all the terms shifted to the right. You can obtain its formula either by starting with its general term (which is $n^2 - n$) and then finding its sum or just by replacing all the $n$'s in the formula I obtained by $n-1$ (this works because all the terms are shifted to the right and the first term is $0$). – Alraxite Apr 21 '13 at 0:22

HINT:

\begin{align*} 1\cdot2+2\cdot3+\ldots+n(n+1)&=2\binom22+2\binom32+\ldots+2\binom{n+1}2\\ &=2\left(\binom22+\binom32+\ldots+\binom{n+1}2\right)\;, \end{align*}

and you can apply the Christmas stocking (or hockey stick) identity, if you know it. (If not, you might also want to look at this demonstration.)

As I have been directed to teach how to fish... this is a bit clunky, but works. Define rising factorial powers: $$x^{\overline{m}} = \prod_{0 \le k < m} (x + k) = x (x + 1) \ldots (x + m - 1)$$ Prove by induction over $n$ that: $$\sum_{0 \le k \le n} k^{\overline{m}} = \frac{n^{\overline{m + 1}}}{m + 1}$$ When $n = 0$, it reduces to $0 = 0$.

Assume the formula is valid for $n$, and: \begin{align*} \sum_{0 \le k \le n + 1} k^{\overline{m}} &= \sum_{0 \le n} k^{\overline{m}} + (n + 1)^{\overline{m}} \\ &= \frac{n^{\overline{m + 1}}}{m + 1} + (n + 1)^{\overline{m}} \\ &= \frac{n \cdot (n + 1)^{\overline{m}} + (m + 1) (n + 1)^{\overline{m}}} {m + 1} \\ &= \frac{(n + m + 1) \cdot (n + 1)^{\overline{m}}}{m + 1} \\ &= \frac{(n + 1)^{\overline{m + 1}}}{m + 1} \end{align*} By induction, it is valid for all $n$.

Defining falling factorial powers: $$x^{\underline{m}} = \prod_{0 \le k < m} (x - k) = x (x - 1) \ldots (x - m + 1)$$ you get a similar formula for the sum: $$\sum_{0 \le k \le n} k^{\underline{m}}$$

You can see that $x^{\overline{m}}$ (respectively $x^{\underline{m}}$) is a monic polynomial of degree $m$, so any integral power of $x$ can be expressed as a combination of appropiate factorial powers, and so sums of polynomials in $k$ can also be computed with some work.

By the way, the binomial coefficient: $$\binom{\alpha}{k} = \frac{\alpha^{\underline{k}}}{k!}$$

Check for a relationship between $n (n + 1) (n + 2)$ and your sum by checking small cases and prove it by induction.

• I think finding a candidate for the solution in questions like this is the hard part. You have not made it any easier for OP the next time he's faced with a similar problem. So here's my side comment: since each term $a_i$ in the sum is a second-degree polynomial in $i$ (in this case $i^2 + i$), the sum is a third degree polynomial in $n$. Now all you have to do is calculate four terms by hand, solve for the coefficients and arrive at an expression that can be tested. This works for any degree polynomials with appropriate generalizations. – Arthur Apr 20 '13 at 23:25
• @Arthur OP is talking about binomial coefficients... maybe this nudges in the right direction. – vonbrand Apr 20 '13 at 23:27
• @Arthur, the right way to solve such is to start with $\sum_{0 \le k \le n} z^n = \dfrac{1 - z^{n + 1}}{1 - z}$, differentiate, and set $z = 1$. – vonbrand Apr 20 '13 at 23:29
• True, but I still believe in the "teach the man to fish"-way of answering, which makes your answer fall a little short. – Arthur Apr 20 '13 at 23:31