11
$\begingroup$

Let $p \in \mathbf{N}$. I don't know how to prove that $\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^j=0 \textrm{ for } j \in \{0,\ldots,p-1\},$ and $\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^p=p!$

(Maybe using the following hint, but not necessarily. Let's consider Cramer's system of equations (where $0^0:=1$): $0^j x_0+1^j x_1+\ldots + p^j x_p=p! \delta_{j,p}$

($j=0, \ldots,p$). The solution is probably given by $x_i=(-1)^{p-i} {p \choose i}$ for $i=0,\ldots, p$.)

Thanks.

  • 1
    See also the proofs [here](http://math.stackexchange.com/questions/18688/proof-of-a-combination-identity-sum-j-0n-1jn-choosej-left1-frac), which is basically the same question.2011-09-30

5 Answers 5

4

Note that $\displaystyle\binom{p}{i}\binom{i}{k}=\binom{p}{k}\binom{p-k}{i-k}$, Therefore, $ \begin{align} \sum_i(-1)^i\binom{p}{i}\binom{i}{k} &=\sum_i(-1)^i\binom{p}{k}\binom{p-k}{i-k}\\ &=\binom{p}{k}(1-1)^{p-k}\\ &=\binom{p}{k}0^{p-k}\tag{1} \end{align} $ Which is $1$ when $k=p$ and $0$ when $k. Thus, $\displaystyle T_pf=\sum_i(-1)^i\binom{p}{i}f(i)$ kills all combinatorial polynomials with degree less than $p$.

$\displaystyle k!\binom{i}{k}$ is a degree $k$ polynomial in $i$ with lead coefficient $1$. Thus, we can write $ i^j=j!\binom{i}{j}+\sum_{k=0}^{j-1}a_{jk} k!\binom{i}{k}\tag{2} $ for some integers $a_{jk}$. Therefore, putting together $(1)$ and $(2)$, $ \begin{align} \sum_i(-1)^i\binom{p}{i}i^j &=\sum_i(-1)^i\binom{p}{i}\left(j!\binom{i}{j}+\sum_{k=0}^{j-1}a_k k!\binom{i}{k}\right)\\ &=j!\binom{p}{j}0^{p-j}+\sum_{k=0}^{j-1}a_kk!\binom{p}{k}0^{p-k}\\ &=\left\{\begin{array}{rl}0&\text{if }j

  • 0
    @J. M.: Yes, it is. I had started mine a while ago, so I didn't see yours until after I had finished mine.2011-09-23
10

Use generating functions.

Call $s_{j,p}$ the $j$th sum and consider the exponential generating function $S_p$ of the sequence $(s_{j,p})_{j\geqslant0}$ defined as $ S_p(x)=\sum\limits_{j=0}^{+\infty}s_{j,p}\frac{x^j}{j!}=\sum\limits_{i=0}^p(-1)^{p-i}{p\choose i}\sum\limits_{j=0}^{+\infty}i^j\frac{x^j}{j!}=\sum\limits_{i=0}^p(-1)^{p-i}{p\choose i}\mathrm e^{ix}. $ By the binomial theorem, the last sum is $ \sum\limits_{i=0}^p{p\choose i}a^ib^{p-i}=(a+b)^p, $ for $a=\mathrm e^x$ and $b=-1$, hence $ S_p(x)=(\mathrm e^x-1)^p. $ The series expansion of $\mathrm e^x-1$ has no $x^0$ term hence the valuation of $S_p(x)$ is at least $p$. This proves that $s_{j,p}=0$ for every $0\leqslant j\leqslant p-1$.

Furthermore $\mathrm e^x-1=x+o(x)$ hence the $x^p$ term in $S_p(x)$ is exactly $1$ and $s_{p,p}=p!$.

This method provides $s_{p+j,p}$ for every positive $j$ as well, for example, $ \frac{s_{p+1,p}}{(p+1)!}=\frac{p}2,\qquad \frac{s_{p+2,p}}{(p+2)!}=\frac{p(3p+1)}{24}, $ and, more generally, for every nonnegative $j$, the ratio $\dfrac{s_{p+j,p}}{(p+j)!}$ is a polynomial in $p$ of degree $j$ and with rational coefficients.

Remark To compute $S_p(x)$, one can also note that the sum at the end of our first displayed equation is a multiple of the expectation of the sum $X_p=Y_1+\cdots+Y_p$ of $p$ i.i.d. Bernoulli random variables $Y_k$ with expectation $x$, hence $ S_p(x)=2^p(-1)^p\mathrm E((-1)^{X_p}\mathrm e^{xX_p}). $ By independence the expectation is a product of $\mathrm E((-1)^{Y_k}\mathrm e^{xY_k})=\frac12(1-\mathrm e^x)$, hence $ S_p(x)=(-1)^p(1-\mathrm e^x)^p=(\mathrm e^x-1)^p. $

  • 0
    @Zarrax, yes. Added this to the post.2011-09-23
7

Another Solution could be as follows:

It's a double counting of the surjective functions from the set $\{1,\dots,j\}$ to the set $\{1,\dots, p\}$.

On one hand, clearly these functions are $p!$ if $j=p$, while there are no such functions if $j.

Let's count these functions in a different way:

For $1\leq i\leq p$ let us define the sets A_i:=\{\text{the functions from }\{1,\dots,j\}\text{ to }\{1,\dots,p\}\text{ which doesn't contain }\; i\;\text{ in their image}\}.

We have then

$\begin{align} |A_i|&=(p-1)^j\\ |A_i\cap A_l|&=(p-2)^j\\ &\vdots&\\ \left|\bigcap_{i=1}^p A_i\right|&=0.\end{align}$

We are interested in calculate the following: $|\overline{A_1}\cap\overline{A_2}\cap\dots\cap\overline{A_p}|=|\overline{A_1\cup A_2 \cup\dots\cup A_p}|= p^j-|A_1\cup A_2 \cup\dots\cup A_p|= $ $p^j-\sum_{i=1}^p\left((-1)^{i+1}\sum_{1\leq j_1<\dots From which the thesis follows.

EDIT Since I spent a lot of time on this problem a year ago, I would like to give two other pennies on the topic, and I would give another solution, or at least a sketch of it:

So, let us consider the differential operator which realizes: $D(f(x)) = \frac{\mathrm d}{\mathrm dx}(x\cdot f(x)) = f(x) + x\cdot\frac{\mathrm df}{\mathrm dx}.$ Immediately one sees that $D(x^m)=m\cdot x^m,$ hence $\sum_{k=0}^{p}(-1)^k \binom{p}{k}\,k^j = \left.D^j\left((1-x)^p\right)\right|_{x=1}.$ So, (almost) immediately, again the thesis follows.


Let me say one last thing. This formula is strictly related to Stirling numbers of the second kind, but note how the second proof I gave you does not say much on what happens if $j>p$, while the first fits perfectly even in this situation.

  • 2
    As it turns out, OP's problem, when recast in the notation of Stirling subset numbers, becomes the matter of proving that \left\{j \atop p\right\}=\begin{cases}0 &\text{if } j < p\\1 &\text{if } j=p\end{cases}. Recast in the language of difference calculus, this just says that if j < p, the $p$-th difference of $x^j$ is 0, much akin to the continuous case...2011-09-23
5

Let $\Sigma$ be an alphabet of $p$ different letters. I claim that $\sum\limits_{i=0}^p (-1)^{p-i} \binom{p}{i} i^j$ counts the number of words over $\Sigma$ of length $j$ that use all $p$ of the letters at least once each. This is just the inclusion-exclusion principle. For each $i$ from $0$ through $p$ there are $\binom{p}{i}i^j$ ways to choose a subset of $i$ letters and form a $j$-letter word using only letters from that subset, but not all of these ways use all $i$ of the letters in the subset. Thus, $\binom{p}{p}p^j = p^j$ is only a first approximation. From that we subtract the words that use only $p-1$ of the letters to get a second approximation, $\binom{p}{p}p^j - \binom{p}{p-1}(p-1)^j.$ Of course every word that’s missing at least two of the letters has been subtracted too often, so we have to add those back in to get a third approximation, $\binom{p}{p}p^j - \binom{p}{p-1}(p-1)^j + \binom{p}{p-2}(p-2)^j.$ The final result after all of the corrections is made is the original sum, $\sum\limits_{i=0}^p (-1)^{p-i} \binom{p}{i} i^j.$

Your result is an immediate consequence: if $j \in \{0,1,\dots,p-1\}$, there are of course no words of length $j$ that use all $p$ letters, and if $j=p$, the words that use all $p$ letters are precisely the $p!$ permutations of $\Sigma$.

  • 0
    I've seen this proved many ways, but this is the first time I've seen it proven using the inclusion-exclusion principle. Cool!2011-09-23
4

A comparison with the definition of the $p$-th forward difference shows that

$\sum_{j=0}^p (-1)^{p-j} \binom{p}{j} j^k=\left.\Delta^p x^k\right\vert_{x=0}$

Now, $x^k$ can be expanded as a series of falling factorials:

$x^k=\sum_{j=0}^k \left\{k \atop j\right\} x^{(j)}$

where $\left\{n \atop j\right\}$ is a Stirling subset number. Thus,

$\Delta^p x^k=\sum_{j=0}^k \left\{k \atop j\right\}\Delta^p x^{(j)}$

where we used the linearity of the forward difference operator. Since

$\Delta^p x^{(k)}=\left(\prod_{j=0}^{p-1} (k-j)\right)x^{(k-p)}$

and the product becomes zero if $k < p$, $\Delta^p x^{(k)}=0$ if $k < p$. Similarly, if $k=p$, the product in front is equal to $p!$, and we also have the property $x^{(0)}=1$; thus, $\Delta^p x^{(p)}=p!$. Substituting those into the expansion of $x^k$ in terms of the $x^{(j)}$, and noting that $\left\{k \atop k\right\}=1$, the claim is proven.

  • 0
    A funny bit about *Mathematica*: it knows how to evaluate `Sum[(-1)^j Binomial[p, j] (p - j)^n, {j, 0, p}]` but is completely stumped by the reversal `Sum[(-1)^(p - j) Binomial[p, j] j^n, {j, 0, p}]`. Hmm...2011-09-24