Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Thanks for very nice proofs. –  Richard Sep 24 '11 at 7:41
1  
See also the proofs here, which is basically the same question. –  Mike Spivey Sep 30 '11 at 15:36

5 Answers 5

up vote 7 down vote accepted

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

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<j_i\leq p}\left|\bigcap_{k=1}^i A_{j_k}\right|\right)=\sum_{k=0}^p(-1)^{p+k}\binom{p}{k}k^j.$$ 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.

share|improve this answer
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... –  J. M. Sep 23 '11 at 10:20

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

share|improve this answer
2  
You can shorten this by observing the formula for $S_p(x)$ at the end of the first displayed line is just the binomial expansion of $(e^x - 1)^p$. –  Zarrax Sep 23 '11 at 14:03
    
@Zarrax, yes. Added this to the post. –  Did Sep 23 '11 at 15:09

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

share|improve this answer
    
I've seen this proved many ways, but this is the first time I've seen it proven using the inclusion-exclusion principle. Cool! –  robjohn Sep 23 '11 at 15:08

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.

share|improve this answer
1  
More generally, this argument shows that $\sum_{j=0}^p (-1)^{p-j} {p \choose j} j^k = \left\{k \atop p\right\} p!$, which holds for all nonnegative integers $k$. –  Mike Spivey Sep 23 '11 at 15:57
    
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... –  J. M. Sep 24 '11 at 5:47

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<p$. 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<p\\p!&\text{if }j=p\end{array}\right.\tag{3} \end{align} $$

share|improve this answer
    
More or less similar to my approach, since $k!\binom{i}{k}=i^{(k)}$... the $a_k$ in equation $(2)$ are the Stirling subset numbers, as I mentioned in my answer. –  J. M. Sep 23 '11 at 15:02
    
@J. M.: Yes, it is. I had started mine a while ago, so I didn't see yours until after I had finished mine. –  robjohn Sep 23 '11 at 15:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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