Prove $\sum_{i=0}^n (-1)^{n-i} \binom{n+1}{i} (i+1)^n = (n+2)^n$ I found through simulations that 

$$\sum_{i=0}^n (-1)^{n-i} \binom{n+1}{i} (i+1)^n  = (n+2)^n$$

Is there any proof of this?  I've tried to solve it by:


*

*Induction, but it gets too messy.

*Binomial theorem, but I got nowhere.


Any help with this is highly appreciated. 
 A: Let $[m]$ denote the set of the first $m$ positive integers.
Let $S$ be the set of functions from $[n]\to [n+2]$, and for $1\le i \le n+1$, let $S_i$ be the set of such functions whose range does not contain $i$. Obviously, $|S|=(n+2)^n$. Furthermore, the range of a function in $S$ will not contain at least two elements, since the range has at most $n$ elements. Therefore, some number $1\le i\le n+1$ must be missing from the range, so
$$
S=\bigcup_{i=1}^{n+1} S_i
$$ 
Therefore, we can use the principle of inclusion-exclusion to count $|S|$ in terms the sizes of the $k$-way intersections $|S_{i_1}S_{i_2}\dots S_{i_k}|$. For any $k$, the intersection of $k$ of the sets $S_i$ consists of functions whose range does not contain a particular $k$ elements. The number of such functions is $(n+2-k)^n$. Therefore, using the inclusion-exclusion formula,
$$
|S|=(n+2)^n = \sum_{k=1}^{n+1} (-1)^{k+1}\binom{n+1}k(n+2-k)^n
$$
The result follows by reversing the order of the summation, i.e. setting $k\leftarrow n+1-i$.
A: Start from
$$\sum_{q=0}^n (-1)^{n-q} {n+1\choose q} (q+1)^n
\\ = \sum_{q=0}^n (-1)^{n-q} {n+1\choose q} n! [z^n] \exp((q+1)z)
\\ = n! [z^n] \exp(z)
\sum_{q=0}^n (-1)^{n-q} {n+1\choose q} \exp(qz)
\\ = - n! [z^n] \exp(z) \times (-1) \exp((n+1)z)
\\ + n! [z^n] \exp(z)
\sum_{q=0}^{n+1} (-1)^{n-q} {n+1\choose q} \exp(qz)
\\ = n! [z^n] \exp((n+2)z)
\\ - n! [z^n] \exp(z)
\sum_{q=0}^{n+1} (-1)^{n+1-q} {n+1\choose q} \exp(qz)
\\ = (n+2)^n
\\ - n! [z^n] \exp(z) (\exp(z)-1)^{n+1}.$$
Now $\exp(z)-1  = z +  \cdots$ and hence $(\exp(z)-1)^{n+1}  = z^{n+1}
+\cdots$ and therefore
$$[z^n] \exp(z) (\exp(z)-1)^{n+1} = 0$$
and we are left with
$$\bbox[5px,border:2px solid #00A000]{ (n+2)^n.}$$
A: Posting a second answer because there is a completely different, more direct proof. 
Note that subtracting the $(n+2)^n$ on the right over, this is equivalent to proving 
$$
\sum_{i=0}^{n+1} (-1)^{n-i}\binom{n+1}i(i+1)^n\stackrel{?}=0
$$
which after multiplying both sides by $(-1)^n$ equals
$$
\sum_{i=0}^{n+1} (-1)^{i}\binom{n+1}i(i+1)^n \stackrel{?}=0\tag{1}
$$
To prove this, consider the polynomial
$$
\sum_{i=0}^{n+1} \binom{n+1}i(i+1)^nx^i \tag{2}
$$
I claim that $(2)$ is the result of taking the polynomial
$$
\sum_{i=0}^{n+1}  \binom{n+1}ix^i\tag{3}
$$
and performing the following operation $n$ times: multiply the polynomial by $x$, then differentiate. Indeed, each summand of a polynomial looks like $a_i x^i$, and when you multiply by $x$ and differentiate, the result is $(i+1)a_ix^i$. Doing this $n$ times results in $(i+1)^na_ix^i$.
But the polynomial in $(3)$ is by the binomial theorem equal to $(1+x)^{n+1}$. Note that this has a zero of order $n+1$ at $x=-1$. Multiplying by $x$ does not change this. It is a standard result that if $f(x)$ has a zero of order $k$ at $x_0$, then $f'(x)$ has a zero of order $k-1$ at $x_0$. Therefore, since $(3)$ has a zero of order $n+1$, it follows that after $n$ differentiations (and some multiplications by $x$), it will still have a zero of order $1$. In particular, $(2)$ has a zero at $x=-1$, so the expression in $(1)$ equals zero.
A: This is a less clever algebraic proof by induction. We actually prove something stronger:

For any $\lambda>0$, we have
  $$\sum_i(-1)^i\binom{n+1}{i}(i+\lambda)^n=0$$
  where $i$ runs through all integers and define $\binom{n}{i}=0$ if $i<0$ or $i>n$.

Proof. This is straight-forward for $n=0$. Suppose for $n=k$ the statement is true. Then
\begin{align}
\sum_i(-1)^i\binom{k+2}i(i+\lambda)^{k+1}&=\sum_i(-1)^i\binom{k+2}i\binom i1(i+\lambda)^k+\lambda\sum_i(-1)^i\binom{k+2}{i}(i+\lambda)^k
\end{align}
Note that $\binom{k+2}i\binom i1=\binom{k+2}1\binom{k+1}{i-1}$ and $\binom{k+2}i=\binom{k+1}i+\binom{k+1}{i-1}$. By induction hypothesis we obtain $\sum(-1)^i\binom{k+1}i(i+\lambda)^k=0$, thus
\begin{align}
\sum_i(-1)^i\binom{k+2}i(i+\lambda)^{k+1}&=(k+2+\lambda)\sum_i(-1)^i\binom{k+1}{i-1}(i+\lambda)^k\\
&=-(k+2+\lambda)\sum_i(-1)^i\binom{k+1}{i}(i+\lambda+1)^k\\
&=0
\end{align}
where the last equality follows from induction hypothesis again.
