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

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$.

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.}$$

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.