2
$\begingroup$

How can we simplify $\sum_{i=0}^n(-1)^i { n \choose i } (n - i)^3$?

I started computing the first values to figure the pattern:

$\sum_{i=0}^0(-1)^i { 0 \choose i } (0 - i)^3 = 0$

$\sum_{i=0}^1(-1)^i { 1 \choose i } (1 - i)^3 = 1 + 0 = 1$

$\sum_{i=0}^2(-1)^i { 2 \choose i } (2 - i)^3 = 2^3 - 2 + 0 = 6$

$\sum_{i=0}^3(-1)^i { 3 \choose i } (3 - i)^3 = 3^3 -3 \cdot 2^3+3-0 = 6 $

The results don't lead to a pattern and so I thought I must be missing something.

I know that $\sum_{i=0}^n(-1)^i { n \choose i } = 0$ but this also doesn't help.

How to go forth here to solve this (finding a form without the $\Sigma$)?

$\endgroup$

3 Answers 3

5
$\begingroup$

The result is related to the Stirling number of the second kind: $$ n!{3 \brace n}. $$ Particularly for $n>3$ all values are $0$.

$\endgroup$
4
$\begingroup$

I will re-index the sum for personal taste.

The trick here, from the theory of generating functions, is to write $k^3$ as the linear differential operator $(x\frac{\partial}{\partial x})$ applied thrice to the power $x^k$, then evaluated at $x=1$. Then

$$ \sum_{k=0}^n (-1)^k \binom{n}{k}k^3=\left(x\frac{\partial}{\partial x}\right)^3\left.\sum_{k=0}^n (-1)^{n-k}\binom{n}{k}x^k\right|_{x=1} $$

$$ = \left.\left(x\frac{\partial}{\partial x}\right)^3 (x-1)^n\right|_{x=1} $$

Funnily enough, if $n>3$ then all of the derivatives of $(x-1)^n$ above (using the product rule multiple times) will still retain a $(x-1)$ factor, and so when evaluated at $x=1$ will yield $\Sigma=0$. You will see this pattern if you evaluate the sum for $n=4,5,6,\cdots$ (you will get $0$ each time)!

$\endgroup$
4
$\begingroup$

First note that, for $n\ge 3$, $${ n \choose i }i(i-1)(i-2)=n(n-1)(n-2){ n-3 \choose i-3 }.$$

So, for $n\ge 4$, $$\sum_{i=0}^n(-1)^i { n \choose i } i(i-1)(i-2)=-n(n-1)(n-2)\sum_{j=0}^{n-3}(-1)^j { {n-3} \choose{j} }=0.$$ Similarly $$\sum_{i=0}^n(-1)^i { n \choose i } i(i-1)=\sum_{i=0}^n(-1)^i { n \choose i } i=\sum_{i=0}^n(-1)^i { n \choose i }=0.$$ Therefore, by expanding $(n-i)^3$, $$\sum_{i=0}^n(-1)^i { n \choose i } (n-i)^3=0.$$

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