Prove that ${\sum _{n=0} \binom{2n}{n} x^n} = \frac{1}{\sqrt{1-4x}}$

Question

(a) Prove that $${\sum _{n=0} \binom{2n}{n} x^n} = \frac{1}{\sqrt{1-4x}}$$

(b) Let {$a_n$} be a sequence with the property that ${\sum _{k=0}^n}a_ka_{n-k}= 1$. Calculate the generating function of the sequence and use the result from (a) to find an exact expression for $a_n$.

I know I need to use the generating function of catalan numbers, but I just recently started the topic of generating functions and not sure how to go about proving this.

Answer 1

For (a), you can use the binomial theorem $$(1+x)^\alpha = \sum_{n=0}^\infty \binom{\alpha}{n}x^n$$ for $|x|<1$. If we take $\alpha=-1/2$ and substitute $x$ into $-4x$, then we get $$(1-4x)^{-1/2} = \sum_{n=0}^\infty (-4)^n\binom{-1/2}{n}x^n$$ so we just check that $$\binom{2n}{n} = (-4)^n \binom{-1/2}{n}.$$ but you can check it by direct evaluation. Note that $\binom{\alpha}{n} := \frac{\alpha(\alpha-1)\cdots (\alpha-n+1)}{n!}$.

For (b), let we consider the generating function $$f(x) = \sum_{n=0}^\infty a_nx^n.$$ If we square both sides then $$f(x)^2 = \sum_{n=0}^\infty\left(\sum_{k=0}^n a_ka_{n-k}\right)x^n.$$ (if you don't get how to derive it, try to evaluate some terms.) so $f(x)^2 = \frac{1}{1-x}$ and we get $f(x) = \frac{1}{\sqrt{1-x}}$. Comparing with (a), we can conclude that $a_n = \frac{1}{4^n}\binom{2n}{n}$.