# Understanding a formula for coefficients $a_n$ of the generating function$\sum_{n \ge 0} a_nx^n=\frac{1}{\sqrt{1-x}}$.

(HMMT 2019 Alge/NT 8) I am trying to understand the solution of this problem, but I don’t understand how the condition described in the title lead to $$a_n=\frac{_{2n}C_n}{4^n}$$ Does it have anything to do with generating functions or Taylor Series?

• "HMMT 2019 Alge/NT 8" is completely cryptic to me. Can you explain what information is conveyed there ? – Jean Marie May 25 at 16:26
• I thought it might reference this, but this question isn't there, as Q8 or otherwise. – J.G. May 25 at 16:32
• @JeanMarie We're first trying to find to solve a simple subcase of the problem: evaluating $f(p^x)$ for some prime $p$. We let $a_n=f(p^n)$, satisfying $\sum_{j=0}^{n} a_ja_{n-j}=1$ – Kai May 26 at 3:56

I think you can just use a Taylor series at $$x=0$$, which will converge for $$|x|<1$$. The first term is clearly $$1$$, and the derivative is $$\frac{1}{2}(1-x)^{-3/2}$$, giving $$\frac{1}{2}$$. In general, the $$n$$th derivative will be

$$1\cdot \frac{1}{2}\cdot \frac{3}{2}\cdots \frac{2n-1}{2}=\frac{1\cdot 3\cdot 5\cdots (2n-1)}{2^n}$$

The numerator can be dealt with:

$$(1\cdot 2\cdot 3\cdots (2n-2)\cdot (2n-1) \cdot 2n) / (2\cdot 4\cdots 2n) = \frac{(2n)!}{2^n \cdot n!}.$$

This gives

$$\frac{(2n)!}{2^{2n} \cdot n!}$$

for the $$n$$th derivative at $$0$$. Since we divide by $$n!$$ to get the $$n$$th coefficient we get

$$a_n = \frac{(2n)!}{2^{2n} \cdot (n!)^2}=\frac{(2n)!}{(n!)(2n-n)!}\cdot \frac{1}{2^{2n}} = \frac{_{2n}C_n}{4^n}.$$

• Very well done, but the derivative of $(1-x)^{\frac{-1}{2}}$ is $\frac{1}{2}(1-x)^{\frac{-3}{2}}$ You forgot the negative sign. – Kai May 28 at 0:30

Two aspects:

• We recall the binomial identity (see formula 1.9) \begin{align*} \binom{-\frac{1}{2}}{n}=\frac{(-1)^n}{4^n}\binom{2n}{n}\tag{1} \end{align*}

• We apply the binomial series expansion and obtain with (1) \begin{align*} \frac{1}{\sqrt{1-x}}&=(1-x)^{-\frac{1}{2}}\\ &=\sum_{n\geq 0}\binom{-\frac{1}{2}}{n}(-1)^nx^n\\ &=\sum_{n\geq 0}\binom{2n}{n}\frac{1}{4^n}x^n \end{align*}

Notations : Hereafter, I use $$\binom{2n}{n}$$ instead of notation $$_{2n}C_n$$.

Let us give a proof using the rather classical generating function

$$\dfrac12(1-\sqrt{1-4x})=\sum_{n=0}^{\infty}C_nx^n\tag{1}$$

of Catalan numbers :

$$C_n:=\dfrac{1}{n+1}\binom{2n}{n}\tag{2}$$

(see http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec01.pdf for a proof).

Indeed, by differentiation, (1) gives

$$(1-4x)^{-1/2}=\sum_{n=1}^{\infty}nC_nx^{n-1}\tag{3}$$

Shifting indices in the RHS of (3), we get :

$$\dfrac{1}{\sqrt{1-4x}}=\sum_{n=0}^{\infty}(n+1)C_nx^{n}\tag{4}$$

Setting $$X:=4x$$, we finally obtain, using (2) :

$$\dfrac{1}{\sqrt{1-X}}=\sum_{n=0}^{\infty}\binom{2n}{n}\left(\dfrac{X}{4}\right)^n\tag{5}$$

Why is this connection with Catalan numbers hopefuly of interest ? Because these numbers have versatile combinatorial interpretations. See for that the wonderfully illustrated Wikipedia article https://en.wikipedia.org/wiki/Catalan_number.