Is there a shortcut for calculating summations such as this? [duplicate]

Possible Duplicate:
Computing $\sum_{i=1}^{n}i^{k}(n+1-i)$

I'm curious in knowing if there's an easier way for calculating a summation such as

$\sum_{r=1}^nr(n+1-r)$

I know the summation $\sum_{r=1}^xr(n+1-r)$ is going to be a cubic equation, which I should be able to calculate by taking the first few values to calculate all the coefficients. Then I can plug in $n$ for $x$ to get the value I'm looking for. But it seems like there must be an easier way.

In the meantime, I'll be calculating this the hard way.

-

marked as duplicate by Ross Millikan, Pedro Tamaroff♦, Kannappan Sampath, J. M., Zev ChonolesApr 24 '12 at 13:19

If you already know the summations for consecutive integers and consecutive squares, you can do it like this:

\begin{align*} \sum_{r=1}^n r(n+1-r)&=\sum_{r=1}^nr(n+1)-\sum_{r=1}^nr^2\\ &=(n+1)\sum_{r=1}^nr-\sum_{r=1}^nr^2\\ &=(n+1)\frac{n(n+1)}2-\frac{n(n+1)(2n+1)}6\\ &=\frac16n(n+1)\Big(3(n+1)-(2n+1)\Big)\\ &=\frac16n(n+1)(n+2)\;. \end{align*}

Added: Which is $\dbinom{n+2}3$, an observation that suggests another way of arriving at the result. First, $r$ is the number of ways to pick one number from the set $\{0,\dots,r-1\}$, and $n+1-r$ is the number of ways to pick one number from the set $\{r+1,r+2,\dots,n+1\}$. Suppose that I pick three numbers from the set $\{0,\dots,n+1\}$; the middle number of the three cannot be $0$ or $n+1$, so it must be one of the numbers $1,\dots,n$. Call it $r$. The smallest number must be from the set $\{0,\dots,r-1\}$, and the largest must be from the set $\{r+1,r+2,\dots,n+1\}$, so there are $r(n+1-r)$ three-element subsets of $\{0,\dots,n+1\}$ having $r$ as middle number. Thus, the total number of three-element subsets of $\{0,\dots,n+1\}$ is $$\sum_{r=1}^nr(n+1-r)\;.$$ But $\{0,\dots,n+1\}$ has $n+2$ elements, so it has $\dbinom{n+2}3$ three-element subsets, and it follows that

$$\sum_{r=1}^nr(n+1-r)=\binom{n+2}3=\frac{n(n+1)(n+2)}6\;.$$

-
@anon: Yep, I just caught that. Thanks. – Brian M. Scott Apr 12 '12 at 21:02
I know the formulas for the summation of consecutive integers and consecutive cubes, just not consecutive squares. And it seems like the long way got me the wrong answer. Guess I have a mistake to find... – Mike Apr 12 '12 at 21:18
Ugh... Just saw the added part. That I should have figured out sooner and avoided the summation in the first place. – Mike Apr 12 '12 at 21:31
$\binom{n+2}3$ is also the number of ways to choose 3 not necessarily unique elements from the set $\{1,...,n\}$, which turned out to be more or less what I was doing. – Mike Apr 12 '12 at 22:36

Yes, linearity and a few memorized formulas:

$$\begin{array}{c l} \sum_{r=1}^n r(n+1-r) &=(n+1)\left(\sum_{r=1}^n r\right)-\sum_{r=1}^n r^2 \\ & = (n+1)\frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{6} \\ & = \frac{n(n+1)(n+2)}{6}.\end{array}$$

-

Note that $$r(n+1-r)=n\binom{r}{1}-2\binom{r}{2}\tag{1}$$ Using the identity $$\sum_r\binom{n-r}{a}\binom{r}{b}=\binom{n+1}{a+b+1}\tag{2}$$ with $a=0$, we can sum $(2)$ for $r$ from $1$ to $n$ and get $$n\binom{n+1}{2}-2\binom{n+1}{3}\tag{3}$$ Formula $(3)$ can be manipulated into more convenient forms, e.g. $$\left((n+2)\binom{n+1}{2}-2\binom{n+1}{2}\right)-2\binom{n+1}{3}\\[18pt] 3\binom{n+2}{3}-\left(2\binom{n+1}{2}+2\binom{n+1}{3}\right)\\[18pt] 3\binom{n+2}{3}-2\binom{n+2}{3}$$ $$\binom{n+2}{3}\tag{4}$$

-
Guessing that k in (2) should be an r? – Mike Apr 13 '12 at 0:48
@Mike: indeed. thanks – robjohn Apr 13 '12 at 2:11