Recently I came across the following identity, but if I try proving it with induction, then I get stuck.

$$n! = \sum^n_{k=0}(-1)^{n-k}\binom{n}{k}(k+1)^n$$

While trying my induction step I get the following:

$$(n+1)! = (n+1)\sum^n_{k=0}(-1)^{n-k}\binom{n}{k}(k+1)^n$$ $$(n+1)! = \sum^n_{k=0}(-1)^{n-k}\binom{n+1}{k+1}(k+1)^{n+1}$$ $$\vdots$$ $$(n+1)! = \sum^{n+1}_{k=0}(-1)^{n+1-k}\binom{n+1}{k}(k+1)^{n+1}$$

(Question) How do I complete the proof?

Thanks in advance.


This is quite tough to show using induction. BUT ...

Using the $[x^k]:f(x)$ to represent the coeficient of $x^k$ in the power series for $f(x)$.

Note that \begin{eqnarray*} \frac{(k+1)^n}{n!} =[x^n]: e^{(k+1)x}. \end{eqnarray*} Now divide your equation by $n!$ and we have \begin{eqnarray*} \sum_{k-0}^{n} (-1)^{n-k} \binom{n}{k}\frac{(k+1)^n}{n!} &=&[x^n]: \sum_{k-0}^{n} (-1)^{n-k} \binom{n}{k} e^{(k+1)x} \\&=& [x^n]:e^x(e^x-1)^n =\color{red}{1}. \end{eqnarray*}


Alternatively, and proceeding from a more general result, we have that the Finite Difference of first order, and the next iterated ones, are defined as $$ \eqalign{ & \Delta _{\,x} f(x) = f(x + 1) - f(x) \cr & \Delta _{\,x} ^n f(x) = \Delta _{\,x} \left( {\Delta _{\,x} ^{n - 1} f(x)} \right) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{n - k} \binom{n}{k}f(x + k)} \cr} $$

Then, if $f(x)$ is a polynomial of degree $n$ $$ \eqalign{ & f(x) = p_{\,n} (x) = a_{\,n} x^{\,n} + a_{\,n - 1} x^{\,n - 1} + \cdots + a_{\,0} = \cr & = n!a_{\,n} \binom{x}{n} + \left( {n - 1} \right)!b_{\,n - 1} \binom{x}{n-1} + \cdots + b_{\,0} \binom{x}{0} \cr} $$ the $n$th order Difference will leave only the leading coefficient in the Newton expression, i.e. $$ \Delta _{\,x} ^n p_{\,n} (x) = n!a_{\,n} \binom{x}{n-n} = n!a_{\,n} $$

This for whichever $p_n(x)$ and in particular for $ x^n$ (then computed at $x=1$).


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.