Is there a simpler proof for the following identity: $\sum_{n=0}^x \frac{(n+x)!}{n!2^n} = x!2^x$

Question

The proof I have constructed for this first proves that $\sum_{n=0}^\infty \frac{(n+x)!}{n!2^n} = 2(x!2^x)$ using what I believe is combinatorial geometry, then proves that the identity above is half of that (also using combinatorial geometry), but I was wondering if there were an easier way to go about this.

Answer 1

The identity to be proved is:

$$ \sum_{{n=0}}^{\infty} \frac{{(n+x)!}}{{n!2^n}} = \frac{{x!}}{{2^x}} $$

To demonstrate this, consider the following derivation. Let $ S = \sum_{{n=0}}^{\infty} \frac{{(n+x)!}}{{n!2^n}} $. Observe that:

$$ S = \frac{{(x+0)!}}{{0!2^0}} + \frac{{(x+1)!}}{{1!2^1}} + \frac{{(x+2)!}}{{2!2^2}} + \ldots $$

Now, multiply both sides of the equation by 2:

$$ 2S = \frac{{(x+0)!}}{{0!2^{-1}}} + \frac{{(x+1)!}}{{1!2^0}} + \frac{{(x+2)!}}{{2!2^1}} + \ldots $$

Continuing this pattern, each term in the series becomes a term in the expansion of $ (x+n+1)! $ divided by $ (n+1)!2^n $:

$$ 2S = \frac{{x!}}{{0!2^{-1}}} + \frac{{(x+1)!}}{{1!2^0}} + \frac{{(x+2)!}}{{2!2^1}} + \ldots $$

Simplify each term:

$$ 2S = 2(x!2^1) $$

Divide by 2:

$$ S = \frac{{x!}}{{2^x}} $$

Answer 2

Consider the following power series whose radius of convergence is $2$: $$ \sum_{n=0}^{+\infty} \frac {z^n} {2^n} = \frac 1 {1-\frac z 2}.$$ One can prove by induction that its derivative of order $k$ (sorry but $x$ is not the best choice for an integer :) is \begin{align*} \sum_{n=k}^{+\infty} n(n-1)\cdots(n-(k-1))\frac {z^{n-k}} {2^n} &= \sum_{n=0}^{+\infty} (n+k)(n+k-1)\cdots(n+1)\frac {z^n} {2^{n+k}} \\ &= \frac 1 {2^k} \sum_{n=0}^{+\infty} \frac{(n+k)!} {n!2^n} z^n,\end{align*} and with the right-hand term: $$ \left( -\frac 1 2\right)^k \times \frac{(-1)^k \times k!} {\left(1-\frac z 2\right)^{k+1}}.$$ Evaluating each expression at $z=1$ yields $$ \frac 1 {2^k} \sum_{n=0}^{+\infty} \frac{(n+k)!} {n!2^n} = \frac 1 {2^k} \times 2^{k+1} k!,$$ and simplifying by $1/2^k$ yields the result for the whole sum.

The same reasoning allows to compute the half sum. Consider for that the polynomial $$ \sum_{n=0}^{2k} \frac {z^n} {2^n} = \frac {1-\left(\frac z 2\right)^{2k+1}} {1-\frac z 2}.$$ As before we differentiate $k$ times. The sum yields a similar result (with $0\leq n\leq k$). We only need to investigate the right-hand term. We will use the following differentiation rule: $$ (f\times g)^{(k)} = \sum_{i=0}^k \binom{k}{i} f^{(i)} g^{(k-i)}$$ with $f(z):= 1-(z/2)^{2k+1}$ and $g(z)=1/(1-z/2)$. I separate the constant in $f$ in the case $i=0$ to obtain $$ \left( -\frac 1 2\right)^k \frac{(-1)^k k!} {\left(1-\frac z 2\right)^{k+1}} - \sum_{i=0}^k \binom{k}{i} \frac {(2k+1)!} {(2k+1-i)!} \frac 1 {2^i}\left(\frac z 2\right)^{2k+1-i} \frac 1 {(-2)^{k-i}}\frac{(-1)^{k-i} (k-i)!} {\left(1-\frac z 2\right)^{k-i+1}},$$ and thus at $z=1$: $$ 2k! - \sum_{i=0}^k \binom{k}{i} \frac {(2k+1)!} {(2k+1-i)!} \frac 1 {2^{2k+1-i}} \frac {2^{k-i+1}} {2^k} (k-i)! \\ = 2k! - \frac {k!} {4^k} \sum_{i=0}^k \binom{2k+1}{i}.$$ We can prove without much trouble that the sum is equal to $4^k$ (see this post for instance), which proves that the above difference is equal to $k!$ and concludes the proof up to a multiplication by $2^k$.

Answer 3

Consider the discrete random variable $Y\sim\mathrm{NB}\left(x,\frac12\right)$. This means that $$\mathrm{P}(Y=n+x)=\binom{n+x}{x-1}\left(\frac12\right)^{n+x-1}$$ Now consider $\mathbb{E}(Y)$. Since $Y=\sum_{i=1}^xY_i$, where $Y_i\sim\mathrm{Geo}\left(\frac12\right)$, $$\begin{align}\mathbb{E}(Y)&=\mathbb{E}\left(\sum_{i=1}^xY_i\right)\\&=\sum_{i=1}^x\mathbb{E}(Y_i)\\&=\sum_{i=1}^x2\\&=2x\end{align}$$ However, $\mathbb{E}(Y)$ can also be written as $$\begin{align}\mathbb{E}(Y)&=\sum_{n=0}^\infty(n+x)\mathrm{P}(Y=n+x)\\&=\sum_{n=0}^\infty(n+x)\binom{n+x-1}{x-1}\left(\frac12\right)^{n+x}\\&=\sum_{n=0}^\infty\frac{(n+x)(n+x-1)!}{n!(x-1)!}\left(\frac12\right)^{n+x}\\&=\frac1{(x-1)!2^{x}}\sum_{n=0}^\infty\frac{(n+x)!}{n!2^n}\end{align}$$ Since the two values of $\mathbb{E}(Y)$ are equal, it can be easily seen that $$\sum_{n=0}^\infty\frac{(n+x)!}{n!2^n}=2x\cdot(x-1)!2^{x}=x!2^{x+1}\text{,}$$as required.

EDIT: I forgot to address the second part of the question. A similar approach with statistics can also be used.

Consider the discrete random variable $Z\sim\mathrm{NB}\left(x+1,\frac12\right)$. This means that $$\mathrm{P}(Z=n+x+1)=\binom{n+x}{x}\left(\frac12\right)^{n+x+1}$$Now consider the series $\sum_{n=0}^x\frac{(n+x)!}{n!2^n}$:$$\begin{align}\sum_{n=0}^x\frac{(n+x)!}{n!2^n}&=x!2^{x+1}\sum_{n=0}^x\binom{n+x}{x}\left(\frac12\right)^{n+x+1}\\&=x!2^{x+1}\sum_{n=0}^x\mathrm{P}(Z=n+x+1)\\&=x!2^{x+1}\mathrm{P}(Z\le2x+1)\\&=x!2^{x+1}\mathrm{P}(W\ge x+1)\end{align}$$where $W\sim\mathrm{B}\left(2x+1,\frac12\right)$.

By symmetry, $\mathrm{P}(W=w)=\mathrm{P}(W=2x+1-w)$, so we have that $\mathrm{P}(W\ge x+1)=\mathrm{P}(W\le x)$, so $$\begin{align}\mathrm{P}(W\ge x+1)&=\frac12\left(\mathrm{P}(W\le x)+\mathrm{P}(W\ge x+1)\right)\\&=\frac12\mathrm{P}(0\le W\le2x+1)\\&=\frac12\end{align}$$Therefore we can conclude that $$\sum_{n=0}^x\frac{(n+x)!}{n!2^n}=\frac12\cdot x!2^{x+1}=x!2^{x}$$

Answer 4

The Infinite Sum

Keep tossing a fair coin until you get $x+1$ tails. The probability that you get $n$ heads is given by the following:

$$ \binom{x+n}{n}\cdot\frac{1}{2^{x+n+1}} $$

The expression is quite trivial. You toss the coin $x+n+1$ times. Since, the last toss is tail, then $n$ of the first $x+n$ tosses are heads. If we sum up all probabilities, then of course the result equals one:

$$ \sum_{n=0}^{\infty} \binom{x+n}{n}\cdot\frac{1}{2^{x+n+1}}=1 $$

Simple algebraic manipulation yields

$$ \sum_{n=0}^{\infty} \frac{\left(n+x\right)!}{n!2^{n}}=2\left(x!2^{x}\right) $$

The Finite Sum

Now we change the rule. We stop when we toss $x+1$ tails or $x+1$ heads. The probability that we stop because of tails instead of head is obviously $\frac{1}{2}$:

$$ \sum_{n=0}^{x}\binom{x+n}{n}\cdot\frac{1}{2^{x+n+1}}=\frac{1}{2} $$

The sum is only up to $n=x$ because otherwise we would have stop because of heads. Simple algebraic manipulation yields

$$ \sum_{n=0}^{x} \frac{\left(n+x\right)!}{n!2^{n}}=x!2^{x} $$