How can I intuitively get from the below summation to a generating function without knowing key identities before hand?

Question

In class, our professor was very adamant that the following simplification is intuitive: \begin{align*} \sum^{\infty}_{n=0}x^n\binom{2n}{n}=\frac{1}{\sqrt{1-4x}} \end{align*}

I can get from the RHS to the LHS comfortably by using the identity that \begin{align*} \binom{-1/2}{n} &=(-1)^n 2^{-2n}\binom{2n}{n}. \end{align*}

However, I have no idea how to get from the LHS to the RHS without using any special identities (including the one above) or Cauchy's integral formula (I haven't learned about it yet, but someone suggested that this was a valid approach as well). Our professor insisted that we should be able to get the RHS result solely from massaging Taylor's theorem. I really want to make sure I can get these results on my own so I can try exploring other generating functions on my own, but it definitely doesn't feel intuitive in the slightest.

Answer 1

If you write down a few terms: \begin{align*} f(x)=\sum^{\infty}_{n=0}x^n\binom{2n}{n}=1+2x+6x^2+20x^3+70x^4+... \end{align*}

Then, try to play around with it, like square it. $$ [f(x)]^2=1+(2+2)x+(6+4+6)x^2+(20+12+12+20)x^3+(70+40+36+40+70)x^4+...\\ =1+4x+16x^2+64x^3+256x^4+... $$

Luckily you find a G.P. Then $$ [f(x)]^2=\frac{1}{1-4x} $$ But in general, you need to know the series form of many functions in order to guess the answer form. For binomial coefficient type coefficient, maybe square is a good try.

Answer 2

Just follow your professor's hint: let $f(x)=(1-4x)^{-1/2},$ compute the first derivatives, and then guess and prove (by induction) that $$f^{(n)}(x)=\frac{(2n)!}{n!}(1-4x)^{-\frac{2n+1}2}.$$ Hence $$f(x)=\sum_{n=0}^\infty\frac{f^{(n)}(0)}{n!}x^n=\sum_{n=0}^\infty\binom{2n}nx^n$$ as a formal power series, but also as an ordinary power series, with radius of convergence $\frac14.$

Another approach is to start from the LHS: let $a_n=\binom{2n}n,$ then $a_{n+1}=\left(4-\frac2{n+1}\right)a_n.$ Multiplying both sides by $x^{n+1}$ and summing up, you find that the series $f(x):=\sum a_nx^n$ satisfies $$f(x)-1=4xf(x)-2\int_0^xf(t)dt.$$ Solving the corresponding differential equation $(1-4x)f'(x)=2f(x),$ you discover the claimed RHS. For more details, see T. Koshy, Catalan Numbers with Applications, p. 26-28

Answer 3

$$ {1\over 1-4x}=1+4x+16x^2+64x^3+... $$

$$ \left(1+2x+6x^2+...{2n\choose n}x^2+...\right)^2 =\sum_{n=0}^\infty\left(\sum_{i=0}^n{2i\choose i}{2(n-i)\choose n-i}\right)x^n\\ =\sum_{n=0}^\infty 4^nx^n $$ The identity $$ \sum_{i=0}^n{2i\choose i}{2(n-i)\choose n-i}=\left(-{4}\right)^n\sum_{i=0}^n{-1/2\choose i}{-1/2\choose n-i}=\\(-4)^n{-1\choose n}=4^n $$ follows from Vandemonde's identity.

(Credit: I found this compact proof here. There are also many, many other proofs on math.stackexchange.net.)