Friday 23 January 2015

summation - Generating functions and central binomial coefficient




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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...