Proving Combinatorical Summation: $n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$

Question

been stuck with this question for the last few hours, any help would be appreciated.

$$ {\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}} $$

what I did:

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

So we are left to prove $\sum_{k=0}^n\frac{(-1)^k(n-k)^n}{k!(n-k)!}=1$. tried doing so using induction, or treating the sum as geometric sequence (which turned out poorly)

Suggestions?

Answer 1

If $(Δp)(x)=p(x)−p(x-1)$ denotes the step-one difference operator, one gets by repeated application $$ (Δ^np)(x)=\sum_{k=0}^n\binom{n}{k} (-1)^{k} p(x-k) $$ and your expression is equal to $$ n!=(Δ^np)(n) $$ where $p(x)=x^n$.

Now in general, the degree decreases by one in each application of the difference operator, $\deg(Δ^np)=\deg(p)-n$, so that by starting with $\deg p=n$ the result is a constant which only depends on the leading coefficient of $p$. Since $$ Δ(x^m)=x^m-(x-1)^m=mx^{m-1}-\binom{m}2 x^{m-1}+... $$ the leading coefficient of $Δ^kp$ is $p_n\cdot n(n-1)...(n-k+1)$ and thus the leading coefficient of $Δ^np$ is $n!\cdot p_n$.

Answer 2

First, ask yourself the following question: $\quad\displaystyle\sum_{k=0}^na^k{n\choose k}x^{n-k}~=~?\quad$ Hint: See binomial theorem.

Then apply the following two steps repeatedly: $(1).$ Differentiate both sides with respect to x, and

$(2).$ Multiply both sides with x. Notice how, after each two steps, $\bigg(x\dfrac d{dx}\bigg)^k\circ(x-1)^n$ can be

rewritten as $(x-1)^{n-k}\cdot P_k(x)$, where $P_k(x)$ is a polynomial of degree k in x and n. Notice also

that $P_k(1)=n(n-1)\cdots(n-k+1)$. Try to prove these two observations by induction. Then it

is quite evident that $P_n(1)$ will be $n!$

Answer 3

For $j\lt n$, $$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m+k}{j} &=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{i=0}^j\binom{m}{j-i}\binom{k}{i}\tag{1}\\ &=\sum_{i=0}^j\binom{m}{j-i}\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{k}{i}\tag{2}\\ &=\sum_{i=0}^j\binom{m}{j-i}\sum_{k=0}^n(-1)^k\binom{n}{i}\binom{n-i}{k-i}\tag{3}\\ &=\sum_{i=0}^j\binom{m}{j-i}\binom{n}{i}(-1)^i\sum_{k=0}^n(-1)^{k-i}\binom{n-i}{k-i}\tag{4}\\ &=\sum_{i=0}^j\binom{m}{j-i}\binom{n}{i}(-1)^i0^{n-i}\tag{5}\\[9pt] &=0\tag{6} \end{align} $$ Explanation:
$(1)$: Vandermonde Identity
$(2)$: rearrange terms
$(3)$: $\binom{n\vphantom{k}}{k}\!\!\binom{k}{i}=\binom{n\vphantom{k}}{i}\!\!\binom{n-i}{k-i}$ by expansion into factorials
$(4)$: rearrange terms
$(5)$: binomial expansion of $(1-1)^{n-i}$
$(6)$: all terms in the sum are zero

Any polynomial in $m$ of degree less than $n$ can be written as a linear combination of $\binom{m}{j}$ for $j\lt n$. Therefore, if $P(x)$ is a polynomial of degree less than $n$, then $(6)$ says that $$ \sum_{k=0}^n(-1)^k\binom{n}{k}P(m+k)=0\tag{7} $$ Since $\color{#C00000}{k^n-n!\binom{k}{n}}$ is a polynomial in $k$ of degree less than $n$, $$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n &=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\color{#C00000}{k^n}\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\color{#C00000}{n!\binom{k}{n}}\\ &=n!\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\binom{k}{n}\\[9pt] &=n!\tag{8} \end{align} $$ since the only term in the last sum that is not zero is when $k=n$.

Answer 4

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{n! = \sum_{k = 0}^{n}\pars{-1}^{k}{n \choose k}\pars{n - k}^{n}}$

\begin{align} \sum_{k = 0}^{n}\pars{-1}^{k}{n \choose k}\pars{n - k}^{n} &=n!\bracks{\overbrace{\color{#c00000}{% {1 \over n!}\sum_{k = 0}^{n}\pars{-1}^{k}{n \choose k}\pars{n - k}^{n}}} ^{\ds{{\rm S}\pars{n,n} = 1}}} \end{align} The $\color{#c00000}{\ds{\mbox{above red expression}}}$ is the Stirling Number of the Second Kind $\ds{{\rm S}\pars{n,n}}$. See formula $\pars{10}$ in the just cited link.

$\ds{{\rm S}\pars{n,n}}$ is the number of ways of partitioning a set of $\ds{n}$ elements into $\ds{n}$ nonempty sets which is obviously $\large\tt\mbox{equal to one}$.

$$\color{#66f}{\large% n! = \sum_{k = 0}^{n}\pars{-1}^{k}{n \choose k}\pars{n - k}^{n}} $$