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.

Solution 1:

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

Solution 2:

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.

Solution 3:

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

Solution 4:

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.