# Can this summation be proved to equal 1 for any upper bound 0 or greater?

$$\sum_{i=0}^n \frac{(n-i+1)^n (-1)^i}{i!(n-i)!} =1$$

Prove that the summation above always equals 1 for any integer n greater than or equal to zero.

I believe that it probably does equal one always. I've tested low numbers for n and used computers to get slightly higher values confirmed. The problem comes when the factorials and number of terms get to high for accurate computation. I'm looking for a way to prove it is true for all numbers that meet the integer and greater than zero stipulations. If there is a counter example, then that also works to disprove the statement. I'm guessing that simplification of the summation would be useful for a proof, but I've found it very difficult to create a more simplified summation than the one above. If you try out a few numbers, you'll notice that the way that the summation works out to be one is pretty cool.

## 1 Answer

We can show the identity with the help of generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^n]e^{kz}=[z^n]\left(1+kz+\frac{(kz)^2}{2!}+\cdots\right)=\frac{k^n}{n!}\tag{1} \end{align*}

We obtain for integers $n\geq 0$ \begin{align*} \color{blue}{\sum_{i=0}^n\frac{(n-i+1)^n(-1)^i}{i!(n-i)!}} &=\frac{1}{n!}\sum_{i=0}^n\binom{n}{i}(-1)^i(n-i+1)^n\tag{2}\\ &=\frac{1}{n!}\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}(i+1)^n\tag{3}\\ &=\frac{1}{n!}\sum_{i=0}^n\binom{n}{i}n![z^n]e^{(i+1)z}(-1)^{n-i}\tag{4}\\ &=[z^n]e^z\sum_{i=0}^n\binom{n}{i}\left(e^{z}\right)^i(-1)^{n-i}\tag{5}\\ &=[z^n](e^z-1)^ne^z\tag{6}\\ &=[z^n]\left(z+\frac{z^2}{2!}+\cdots\right)^n\left(1+z+\frac{z^2}{2!}+\cdots\right)\tag{7}\\ &\color{blue}{=1} \end{align*} and the claim follows.

Comment:

• In (2) we introduce binomial coefficients since we want to apply the binomial theorem later on.

• In (3) we change the order of summation $i\rightarrow n-i$.

• In (4) we use the coefficient of operator as shown in (1).

• In (5) we do a small simplification.

• In (6) we apply the binomial theorem.

• In (7) we see the smallest power of $z$ is $n$.