3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is $n$? any integer greater than 0? $\endgroup$ – Daniel Montealegre Sep 9 '13 at 22:27
  • $\begingroup$ yes, n is any integer greater than 0 $\endgroup$ – germann Sep 9 '13 at 22:35
  • $\begingroup$ @EduPaz I edited your question, I hope I didn't make any mistakes. $\endgroup$ – Santosh Linkha Sep 9 '13 at 22:44
  • $\begingroup$ 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$. $\endgroup$ – dfeuer Sep 9 '13 at 23:08
  • 1
    $\begingroup$ It's the $k$-th finite difference of a polynomial of degree less than $k$. Therefore it is zero by induction on $k$. $\endgroup$ – Noam D. Elkies Sep 10 '13 at 0:26
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ We are both looking at the repeated difference operator in different ways. (+1) $\endgroup$ – robjohn Sep 10 '13 at 8:41
  • $\begingroup$ @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. $\endgroup$ – achille hui Sep 10 '13 at 9:47
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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