(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?

  • $\begingroup$ "HMMT 2019 Alge/NT 8" is completely cryptic to me. Can you explain what information is conveyed there ? $\endgroup$ – Jean Marie May 25 at 16:26
  • $\begingroup$ I thought it might reference this, but this question isn't there, as Q8 or otherwise. $\endgroup$ – J.G. May 25 at 16:32
  • $\begingroup$ @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$ $\endgroup$ – 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}.$$

  • $\begingroup$ 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. $\endgroup$ – 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


of Catalan numbers :


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

Indeed, by differentiation, (1) gives


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


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.