2
$\begingroup$

How to prove that $$ \sum_{k=0}^n(-1)^{n-k}{n \choose k} k^n = n! $$ using mathematical induction? Please, do not use definition of Stirling number etc. algebra tricks.

$\endgroup$
6
$\begingroup$

Suggested intro: maybe these solutions don't meet the OP's specific requirements, but I think that they're worth making available anyway.


$\color{red}{n!}$ is the number of bijective functions from $A=\{1,2,\ldots,n\}$ to $A$.

Let we say that a function $f:A\to A$ has type $k$ if $|f(A)|=k$. The number of functions with type $\leq n$ is simply given by $n^n$, i.e. the number of all possible functions from $A$ to $A$. The number of functions with type $\leq(n-1)$ is given by $\binom{n}{n-1}$ (the number of ways for choosing $(n-1)$ elements in $A$) times $(n-1)^n$ (the number of functions from $A$ to a set with $(n-1)$ elements).
By the inclusion-exclusion principle, the number of functions with type $n$ (i.e. the number of bijective functions) is given by:

$$ n^n-\binom{n}{n-1}(n-1)^n+\binom{n}{n-1}(n-2)^n-\ldots = \color{red}{\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^n}. $$


Alternative proof. Let $\delta$ be the operator that maps a polynomial $p(x)$ into $p(x+1)-p(x)$.
The following properties are trivial to prove:

  1. If $\partial p$ (the degree of $p$) is $\geq 1$, the degree of $\delta p$ is $\partial p-1$;
  2. If the leading term of $p(x)$ is $a x^n$, the leading term of $\delta p(x)$ is $an x^{n-1}$, i.e. $\delta$ acts on the leading term like the derivative $\frac{d}{dx}$.

Since our sum is just $\delta^n p(0)$ with $p(x)=x^n$, by (2.) it follows that our sum equals $n(n-1)(n-2)\cdots 1 = n!$.

$\endgroup$
  • $\begingroup$ the OP did ask for a solution by induction without tricks :) $\endgroup$ – gt6989b Sep 26 '16 at 16:47
  • 1
    $\begingroup$ @gt6989b: What is the point of doing math avoiding tricks? Tricks are the heart of problem solving. $\endgroup$ – Jack D'Aurizio Sep 26 '16 at 16:49
  • 1
    $\begingroup$ Please don’t delete it; both solutions are worth having around, and (as usual) I’m partial to the first one. What you might do is preface it with a statement to the effect that you realize that these solutions don’t meet the OP’s specific requirements, but you think that they’re worth making available anyway; I’ve done that on occasion. $\endgroup$ – Brian M. Scott Sep 26 '16 at 19:39
  • 1
    $\begingroup$ I like the second proof. It's a bit like what happens with the binomial transform, and the form of the sum suggests making use of it, however it does not work because $k^n$ depends on $n$. $\endgroup$ – Stop hurting Monica Sep 27 '16 at 2:07
  • 1
    $\begingroup$ +1. Nice answer. I'm expecting sometimes in the future a question with the condition "don't write". $\endgroup$ – Felix Marin Sep 27 '16 at 6:52
1
$\begingroup$

Actually carrying out a proof by induction seems to be quite difficult. I found it easiest to prove the following stronger result (by induction on $n$):

$$\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m=\begin{cases} 0,&\text{if }0\le m<n\\ n!,&\text{ if }m=n\;. \end{cases}\tag{1}$$

Assume that $(1)$ holds for a specific $n$. Then

$$\begin{align*} (n+1)!&=(n+1)\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^n\\ &=\sum_{k=0}^n(-1)^{n-k}(n+1-k)\binom{n+1}kk^n\\ &=\sum_{k=0}^n(-1)^{n-k}(n+1)\binom{n+1}kk^n-\sum_{k=0}^n(-1)^{n-k}\binom{n+1}kk^{n+1}\\ &=\sum_{k=0}^n(-1)^{n+1-k}\binom{n+1}kk^{n+1}\\ &\qquad-\sum_{k=0}^n(-1)^{n+1-k}(n+1)\binom{n+1}kk^n\\ &=\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^{n+1}-(n+1)^{n+1}\\ &\qquad-(n+1)\sum_{k=0}^n(-1)^{n+1-k}\binom{n+1}kk^n\\ &=\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^{n+1}-(n+1)^{n+1}\\ &\qquad+(n+1)\sum_{k=0}^n(-1)^{n-k}\left(\binom{n}k+\binom{n}{k-1}\right)k^n\;. \end{align*}$$

We’d like to show that

$$(n+1)!=\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^{n+1}\;,$$

so we’d like to show that

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

or, equivalently, that

$$\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^n=(n+1)^n-\sum_{k=0}^n(-1)^{n-k}\binom{n+1}kk^n=0\;.$$

And in fact

$$\begin{align*} \sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^n&=\sum_{k=0}^{n+1}(-1)^{n+1-k}\left(\binom{n}k+\binom{n}{k-1}\right)k^n\\ &=\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n}kk^n+\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n}{k-1}k^n\\ &=-\sum_{k=0}^{n+1}(-1)^{n-k}\binom{n}kk^n+\sum_{k=0}^n(-1)^{n-k}\binom{n}k(k+1)^n\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}k\big((k+1)^n-k^n\big)\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}k\sum_{m=0}^{n-1}\binom{n}mk^m\\ &=\sum_{m=0}^{n-1}\binom{n}m\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m\\ &=0\;, \end{align*}$$

since by the induction hypothesis

$$\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m=0$$

for $0\le m<n$. This shows that

$$\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^{n+1}=(n+1)!\;,$$

and it only remains to show that

$$\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^m=0\tag{2}$$

when $0\le m\le n$.

Now

$$\begin{align*} \sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^m&=\sum_{k=0}^{n+1}(-1)^{n+1-k}\left(\binom{n}k+\binom{n}{k-1}\right)k^m\\ &=\sum_{k=0}^n(-1)^{n+1-k}\binom{n}kk^m+\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n}{k-1}k^m\\ &=-\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m+\sum_{k=0}^n(-1)^{n-k}\binom{n}k(k+1)^m\;. \end{align*}$$

If $m=n$, this is

$$\begin{align*} -n!+\sum_{k=0}^n(-1)^{n-k}\binom{n}k(k+1)^n&=-n!+\sum_{k=0}^n(-1)^{n-k}\binom{n}k\sum_{\ell=0}^n\binom{n}\ell k^\ell\\ &=-n!+\sum_{\ell=0}^n\binom{n}\ell\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^\ell\\ &=-n!+\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^n+\sum_{\ell=0}^{n-1}\binom{n}\ell\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^\ell\\ &=-n!+n!+\sum_{\ell=0}^{n-1}\binom{n}\ell\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^\ell\\ &=\sum_{\ell=0}^{n-1}\binom{n}\ell\cdot0\\ &=0\;. \end{align*}$$

And if $0\le m<n$, it’s simply

$$\begin{align*} \sum_{k=0}^n(-1)^{n-k}\binom{n}k(k+1)^m&=\sum_{k=0}^n(-1)^{n-k}\binom{n}k\sum_{\ell=0}^m\binom{m}\ell k^m\\ &=\sum_{\ell=0}^m\binom{m}\ell\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m\\ &=\sum_{\ell=0}^m\binom{m}\ell\cdot0\\ &=0. \end{align*}$$

This establishes $(2)$ and concludes the induction step.

$\endgroup$
0
$\begingroup$

HINT

Base Case $n=1$, check whether the equality holds (you should have just 2 terms in the sum)

Inductive Step

Assume this holds for $n = 1, 2, \ldots, N$ and show this for $n = N+1$. You will have to simplify the terms of the summation to express $$ \sum_{k=0}^{N+1} (-1)^{N+1-k}{N+1 \choose k} k^{N+1} $$ in terms of $$ \sum_{k=0}^{N} (-1)^{N-k}{N \choose k} k^{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.