# Evaluating $\sum_{i=0}^k \frac{(-1)^{k-i}k! (n+i)^{k-1}}{i!(k-i)!}$

How to evaluate the the following sum where $n$ is an integer greater than $0$.

$$\sum_{i=0}^k \frac{(-1)^{k-i}k! (n+i)^{k-1}}{i!(k-i)!}$$

I think the answer is $0$, but I can not prove it.

• What is $n$? any integer greater than 0? – Daniel Montealegre Sep 9 '13 at 22:27
• yes, n is any integer greater than 0 – germann Sep 9 '13 at 22:35
• @EduPaz I edited your question, I hope I didn't make any mistakes. – Santosh Linkha Sep 9 '13 at 22:44
• Your answer is wrong. For any $k$, this sum is a polynomial in $n$ with degree $k-1$, so it's not constant as a function of $n$ unless $k=1$. – dfeuer Sep 9 '13 at 23:08
• It's the $k$-th finite difference of a polynomial of degree less than $k$. Therefore it is zero by induction on $k$. – Noam D. Elkies Sep 10 '13 at 0:26

The statement is true, one way to see it is to define a operator $L$ on the spaces of real sequences indexed by $\mathbb{N}$ by:

$$a = (a_k)_{k\in\mathbb{N}} \quad\mapsto\quad L(a)_k = a_{k+1},\;k \in \mathbb{N}$$ i.e. shift the index of the sequence $a$ to the left by one unit. In terms of $L$, the inequality can be formally rewritten as

$$\sum_{i=0}^k (-1)^{k-i} \binom{k}{i} (n+i)^{k-1} = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} L^i(n^{k-1}) = (L - 1)^k(n^{k-1}) = 0$$

This is equivalent to claiming:

Given $n^{k-1}$, a polynomial in $n$ of degree $k-1$, the $k^{th}$ time finite difference of it vanishes.

To prove the statement, it just suffices to observe for any polynomial $P(n)$ of degree $m$, the finite difference of $P(n)$, $P(n+1) - P(n)$, is a polynomial of degree $m-1$.

• We are both looking at the repeated difference operator in different ways. (+1) – robjohn Sep 10 '13 at 8:41
• @robjohn Yup. I do it this way because in the original formula, it is not that obvious those $(n+i)^{k-1}$ terms can be combined as repeated difference operations. – achille hui Sep 10 '13 at 9:47

Let $$P_k(z):=\sum_{i=0}^k\frac{(-1)^{k-i}k!(z+i)^{k-1}}{i!(k-i)!}=(-1)^k\sum_{i=0}^k(-1)^i{k\choose i}(z+i)^{k-1}=(-1)^kQ_k(z),$$ where $$Q_k(z)=\sum_{i=0}^k(-1)^i{k\choose i}(z+i)^{k-1}.$$ Obviously $$Q_1(z)=1-1=0 \quad \forall z$$ For $k \ge 2$ we have \begin{eqnarray} Q_k(z)&=&z^{k-1}+(-1)^k(z+k)^{k-1}+\sum_{i=1}^{k-1}(-1)^i{k\choose i}(z+i)^{k-1}\\ &=&z^{k-1}+(-1)^k(z+k)^{k-1}+\sum_{i=1}^{k-1}(-1)^i\left[{k-1\choose i}+{k-1\choose i-1}\right](z+i)^{k-1}\\ &=&z^{k-1}+\sum_{i=1}^{k-1}(-1)^i{k-1\choose i}(z+i)^{k-1}+\sum_{i=1}^{k-1}(-1)^i{k-1\choose i-1}(z+i)^{k-1}+(-1)^k(z+k)^{k-1}\\ &=&\sum_{i=0}^{k-1}(-1)^i{k-1\choose i}(z+i)^{k-1}+\sum_{i=1}^k(-1)^i{k-1\choose i-1}(z+i)^{k-1}\\ &=&Q_{k-1}(z)-\sum_{i=0}^{k-1}(-1)^i{k-1\choose i}(z+1+i)^{k-1}\\ &=&Q_{k-1}(z)-Q_{k-1}(z+1). \end{eqnarray} Since $Q_1(z)=0$ for every $z$, it follows by induction that $$Q_k(z)=Q_{k-1}(z)-Q_{k-1}(z+1)=0 \quad \forall k \ge 2, \forall z.$$ Thus for every $z$ we have $$P_k(z)=0 \quad \forall k \ge 1.$$

This can be shown using the identities \begin{align} \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\binom{k}{m} &=\left\{\begin{array}{} 0&\text{if }n\ne m\\ 1&\text{if }n=m \end{array}\right.\\[6pt] &=[n=m]\tag{1} \end{align} where $[\dots]$ are Iverson Brackets and $$\sum_{k=0}^m\binom{n}{k}\,\begin{Bmatrix}m\\k\end{Bmatrix}k!=n^m\tag{2}$$ where $\begin{Bmatrix}n\\k\end{Bmatrix}$ is a Stirling number of the second kind. This may look daunting because of the Stirling numbers, but all that $(2)$ really says is that $x^m$ can be written as a linear combination of binomial polynomials $\displaystyle\binom{x}{k}$ of degree $k\le m$.

Then, using $(1)$ and $(2)$, we have for $m\lt n$ \begin{align} \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(x+k)^m &=\sum_{k=0}^n\sum_{j=0}^m(-1)^{n-k}\binom{n}{k}\binom{m}{j}x^{m-j}k^j\\ &=\sum_{k=0}^n\sum_{j=0}^m\sum_{i=0}^j(-1)^{n-k}\binom{n}{k}\binom{m}{j}x^{m-j}\binom{k}{i}\begin{Bmatrix}j\\i\end{Bmatrix}i!\\ &=\sum_{j=0}^m\sum_{i=0}^j\binom{m}{j}x^{m-j}\,[n=i]\,\begin{Bmatrix}j\\i\end{Bmatrix}i!\\ &=\sum_{j=0}^m\binom{m}{j}x^{m-j}\begin{Bmatrix}j\\n\end{Bmatrix}n!\\ &=0 \end{align} since $\displaystyle\binom{m}{j}\begin{Bmatrix}j\\n\end{Bmatrix}=0$ if $m\lt n$.