How to prove that $S(n) = \sum_{k=1}^{n} (-1)^{n-k} k^n\binom{n+1}{n-k} = 1$? I want to show the following:
$$S(n) = \sum_{k=1}^{n} (-1)^{n-k} k^n\binom{n+1}{n-k} = 1$$
I spent hours trying to solve this, unsuccessfully. My main attempt so far, has been trying induction. It trivially holds for $n=1$, and I concluded that $S(n+1) = S(n)$ if the following holds:
$$\sum_{k=1}^{n} (-1)^{n-k} k^n\binom{n+1}{k} = (n+1)^n$$
So I tried induction again, but it turned out to be way harder than I expected. I "know" both of these are true via software. Any help will be appreciated.
 A: The Finite  difference, forward and unitary, of a function
is defined as
$$
\Delta \,f(x) = f(x + 1) - f(x)
$$
and its iterations as
$$
\Delta ^{\,n} \,f(x) = \Delta \left( {\Delta ^{\,n - 1} \,f(x)} \right) = \sum\limits_{k = 0}^n {\left( { - 1} \right)^{\,n - k} \left( \matrix{
  n \cr 
  k \cr}  \right)f(x + k)} 
$$
If $f(x)$ is a polynomial of degree $n$, that is $f(x)=p_n(x)$ then its differences of degree higher than $n$ are all null,
in virtue of the Newton series.
Therefore
$$
\eqalign{
  & 0 = \left. {\Delta ^{\,n + 1} \,x^{\,n} \,} \right|_{\,x\, \in R}  = \sum\limits_{k = 0}^{n + 1} {\left( { - 1} \right)^{\,n + 1 - k} \left( \matrix{
  n + 1 \cr 
  k \cr}  \right)\left( {x + k} \right)^{\,n} }  =   \cr 
  &  =  - \sum\limits_{k = 0}^{n + 1} {\left( { - 1} \right)^{\,n - k} \left( \matrix{
  n + 1 \cr 
  k \cr}  \right)\left( {x + k} \right)^{\,n} }  =   \cr 
  &  =  - \sum\limits_{k = 0}^n {\left( { - 1} \right)^{\,n - k} \left( \matrix{
  n + 1 \cr 
  k \cr}  \right)\left( {x + k} \right)^{\,n} }  - \left( { - 1} \right)\left( \matrix{
  n + 1 \cr 
  n + 1 \cr}  \right)\left( {x + n + 1} \right)^{\,n}  =   \cr 
  &  = \sum\limits_{k = 0}^n {\left( { - 1} \right)^{\,n - k} \left( \matrix{
  n + 1 \cr 
  k \cr}  \right)\left( {x + k} \right)^{\,n} }  - \left( {x + n + 1} \right)^{\,n}  \cr} 
$$
and for $x=0$ in particular.
A: You can prove the second summation combinatorially by counting the number of functions from an $n$-set to an $(n+1)$-set. The RHS is clear. The LHS arises from applying the principle of inclusion-exclusion, where the $n+1$ properties are that element $j$ is not in the image of the function.
A: We seek to show that
$$S(n) = \sum_{k=1}^n (-1)^{n-k} k^n {n+1\choose n-k} = 1.$$
This is
$$\sum_{k=0}^{n-1} (-1)^k (n-k)^n {n+1\choose k}
= 1 + \sum_{k=0}^{n+1} {n+1\choose k} (-1)^k (n-k)^n
\\ = 1 + n! [z^n]
\sum_{k=0}^{n+1} {n+1\choose k} (-1)^k \exp((n-k)z)
\\ = 1 + n! [z^n] \exp(nz)
\sum_{k=0}^{n+1} {n+1\choose k} (-1)^k \exp(-kz)
\\ = 1 + n! [z^n] \exp(nz) (1-\exp(-z))^{n+1}
\\ = 1 + n! [z^n] \exp(-z) (\exp(z)-1)^{n+1} = 1$$
because $\exp(z)-1 = z + \cdots$ and hence $(\exp(z)-1)^{n+1} =
z^{n+1} + \cdots$ which is the claim.
