How would you prove that the generating function of $\binom{2n}{n}$ is $\frac{1}{\sqrt{1-4x}}$?
More precisely, prove that( for $|x|<\frac{1}{4}$ ):
$$\sum^{\infty}_{n=0}x^n\binom{2n}{n}=\frac{1}{\sqrt{1-4x}}$$
Background: I was trying to solve
$$S=\sum^{\infty}_{n=0}\frac{(2n+1)!}{8^n(n!)^2}=\sum^{\infty}_{n=0}\frac{(2n+1)}{8^n}\binom{2n}{n}$$
Which if we let $f(x)$ be the generating function in question, would be simply
$$f(x)+2xf'(x)$$
With $x=\frac{1}{8}$. Is there a simple proof of the first identity? Wikipedia states it without a proper reference (the reference provided states it without proof). Is there an easier way of calculating $S$? (which is $\sqrt{8}$, by the way)
Answer
Here is a simple derivation of the generating function: start with
$$ (1+x)^{-1/2} = \sum_k \binom{-1/2}{k}x^k.$$
Now,
\begin{align*}
\binom{-1/2}{k} &= \frac{\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right)\left(\cdots\right)\left(-\frac{1}{2}-k+1\right)}{k!} \\
&= (-1)^k \frac{1\cdot 3\cdot 5\cdots (2k-1)}{2^k k!} \\
&= (-1)^k \frac{(2k)!}{2^k2^kk!k!} \\
&= (-1)^k 2^{-2k}\binom{2k}{k}.
\end{align*}
Finally replace $x$ by $-4x$ in the binomial expansion, giving
$$
(1-4x)^{-1/2} = \sum_k (-1)^k 2^{-2k}\binom{2k}{k}\cdot (-4x)^k
= \sum_k \binom{2k}{k}x^k.$$
No comments:
Post a Comment