1
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

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