6
$\begingroup$

What is a "simpler" formula for

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

$\endgroup$
10
  • 1
    $\begingroup$ Expand the polynomial, separate out the terms, and use the formulae for sums of powers. $\endgroup$
    – J. M. ain't a mathematician
    Dec 22, 2010 at 5:22
  • 4
    $\begingroup$ The answer to the question asked is "Yes" $\endgroup$
    – Ross Millikan
    Dec 22, 2010 at 5:36
  • 1
    $\begingroup$ @Ross: My mistake. Let me try to correct the question statement. $\endgroup$
    – Aryabhata
    Dec 22, 2010 at 6:01
  • 8
    $\begingroup$ If you are more interested, there is a tool called finite calculus and this is an example of a sum of a falling power. See this document: stanford.edu/~dgleich/publications/finite-calculus.pdf. $\endgroup$
    – J. J.
    Dec 22, 2010 at 6:47
  • 3
    $\begingroup$ ...or read Section 2.6 in Concrete Mathematics by Graham, Knuth & Patashnik. $\endgroup$
    – Hans Lundmark
    Dec 22, 2010 at 7:38

7 Answers 7

Reset to default
16
$\begingroup$

Hint:

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

$\endgroup$
3
  • 6
    $\begingroup$ Let $f(k) = k(k-1)(k-2)(k-3)$. Then $f(k) - f(k-1) = 4(k-1)(k-2)(k-3)$. Summing both sides from $k=3$ to $n$ gives the result. This is an example of a telescoping series. (Do a web search for this term if it is unfamiliar.) $\endgroup$
    – Dave Radcliffe
    Dec 22, 2010 at 6:18
  • $\begingroup$ $\frac{k(k-1)(k-2)(k-3)}{4}$, is this right? $\endgroup$
    – qed
    Dec 24, 2010 at 5:40
  • $\begingroup$ @Craving: You mean $n$ instead of $k$, right? Also, you are forgetting the $6$ in the denominator. $\endgroup$
    – Aryabhata
    Dec 24, 2010 at 7:09
11
$\begingroup$

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

$\endgroup$
0
6
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Why different answer ? What I am missing : Expand[Sum[j^3 - j, {j, 1, n}]] and Expand[Sum[(k - 1) (k - 2) (k - 3), {k, 3, n}]] ? $\endgroup$
    – Quixotic
    Dec 22, 2010 at 6:04
  • 1
    $\begingroup$ @Debanjan: You're missing $\frac{1}{6}$. Also, your first sum should be up to $n-2$, not $n$. $\endgroup$
    – Jonas Meyer
    Dec 22, 2010 at 6:04
  • $\begingroup$ Opps sure $\frac{1}{6}$! but why $n-2$ ? $\endgroup$
    – Quixotic
    Dec 22, 2010 at 6:06
  • $\begingroup$ @Debanjan: Why does the first sum start at $1$ instead of $3$? $\endgroup$
    – Jonas Meyer
    Dec 22, 2010 at 6:08
  • $\begingroup$ I really don't understand what you mean... for the first we have to compute the sum of all values of k from $3$ to $n$ right? $\endgroup$
    – Quixotic
    Dec 22, 2010 at 6:12
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I would say that it's the sum in the question that is the simpler one, since it's a "falling power", and falling powers behave nicer than ordinary powers w.r.t. taking sums and differences (just like ordinary powers are nice when it comes to integrals and derivatives). (See Moron's answer.) $\endgroup$
    – Hans Lundmark
    Dec 22, 2010 at 7:44
  • $\begingroup$ @Hans, By "falling power", do you mean descending powers? Also if the original term you used for "falling power" is in German could please say the German phrase? $\endgroup$
    – jimjim
    Dec 22, 2010 at 22:02
  • 1
    $\begingroup$ It has several names: see de.wikipedia.org/wiki/Fallende_Faktorielle and also en.wikipedia.org/wiki/Pochhammer_symbol. $\endgroup$
    – Hans Lundmark
    Dec 22, 2010 at 22:28
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Also check out this post of mine for some more information about telescoping. $\endgroup$
    – Matt Calhoun
    Dec 22, 2010 at 21:23
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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