6
$\begingroup$

What is a "simpler" formula for

$\sum_{3}^{n} \frac{(k-1)(k-2)(k-3)}{6}$

  • 0
    Many good answers, I really don't know which one to pick.2010-12-24

7 Answers 7

16

Hint:

$k(k-1)(k-2)(k-3) - (k-1)(k-2)(k-3)(k-4) = 4(k-1)(k-2)(k-3)$

  • 0
    @Craving: You mean $n$ instead of $k$, right? Also, you are forgetting the $6$ in the denominator.2010-12-24
11

Show that ${k+3 \choose 3}$ is the number of solutions to $x_1 + ... + x_4 = k$ in non-negative integers. Then $\sum_{k=0}^{n-4} {k+3 \choose 3}$ is the number of solutions to $x_1 + ... + x_5 = n-4$ in non-negative integers, which is...?

6

I really like Aryabhata's hint, but another way to simplify the sum is to reindex with $j=k-2$, and use $(j+1)j(j-1)=j^3-j$.

  • 0
    Oh sorry! now I get your point.Thanks a lot :-)2010-12-22
4

There is no need for a general formula for this special case, all one needs is to use the formulas for $\sum {k} , \sum{k^2} \text{ and } \sum{k^3}$. Just expand the expression and use the simpler known sums.

  • 1
    It has several names: see http://de.wikipedia.org/wiki/Fallende_Faktorielle and also http://en.wikipedia.org/wiki/Pochhammer_symbol.2010-12-22
4

Consider the following sum $\sum_{m=0}^n \binom{m}{k}.$ It counts the number of possibilities to select $k$ elements from at most $n$ elements. Some choices are counted multiple times, for example $\{0,\ldots,k-1\}$ is counted once for each $m \in [k-1,n]$. So it's natural to distinguish among those by tagging them with $m$ somehow. The best way to do that is to add the element $m+1$. The result is a choice of $k+1$ elements from $n+1$, and so $\sum_{m=0}^n \binom{m}{k} = \binom{n+1}{k+1}.$ From this formula one can extract (using linear algebra) the usual formulas for $\sum_{m=0}^n m^k$.

3

HINT $\ $ The sum telescopes since the falling factorial summand is a perfect difference:

$\rm\quad (k+1)^{[n]} - k^{[n]}\ =\ (k+1)\ k\ \cdots\ (k-n+2)\ -\ k\ (k-1)\ \cdots\ (k-n+1)$

$\rm\quad\phantom{(k+1)^{[n]} - k^{[n]}\ } =\ (k+1 - (k-n+1))\ \ \ k\ (k-1)\ \cdots\ (k-n+2)$

$\rm\quad\phantom{(k+1)^{[n]} - k^{[n]}\ }\ =\ n\ k^{[n-1]}$

For other examples of additive/multiplicative telescopy see here and here or here or here or here. For much more on the falling factorials see Steven Roman's textbook The Umbral Calculus.

  • 1
    Also check out [this](http://math.stackexchange.com/questions/$1$370$1$/mathematical-telescoping) post of mine for some more information about telescoping.2010-12-22
2

Perhaps a messy and boring way, we can use the generating function. $\sum_{k=3}^{n}\frac{(k-1)(k-2)(k-3)}{6}=\frac{1}{6}\sum_{k=2}^{n-1}k(k-1)(k-2)$ In addition, the generating function for $k(k-1)(k-2)$ is $x^3\left(\frac{1}{1-x}\right)^{(3)}.$

Hence, the sum is the coefficient of $x^{n-1}$ in $\frac{1}{6}\frac{1}{1-x}x^3\left(\frac{1}{1-x}\right)^{(3)}=\frac{x^3}{(1-x)^5}$, which is $\binom{n-1-3+5-1}{5-1}=\binom{n}{4},\quad n\geqslant3.$