10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I bet induction is not so bad in this case, but I'll try to find a more elegant explanation $\endgroup$ – Exodd Aug 23 '18 at 17:34
  • $\begingroup$ Thanks @Exodd .. Would love to see it through induction. But any other method is also okay. $\endgroup$ – Ahmad Bazzi Aug 23 '18 at 17:35
  • 1
    $\begingroup$ Notice that you can rewrite it as $$ \sum_{i=0}^{n+1} (-1)^{n-i} \binom{n+1}{i} i^{n} =0 $$ $\endgroup$ – Exodd Aug 23 '18 at 18:01
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is outstanding .. Thank you for the clear clarification. I loved both answers. $\endgroup$ – Ahmad Bazzi Aug 23 '18 at 18:37
  • $\begingroup$ Nice answer (+1). $\endgroup$ – Olivier Oloa May 18 at 8:17
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

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.