I got this problem in an exercise list:

Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation:

$$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, C_0=C_1=1.$$

Show that $xG(x)^2 - G(x)+1=0$ and conclude that


Then, show that


What I tried to do:

Since $G(x)=\sum_{n=0}^{\infty}C_nx^n$,we have that $$xG(x)^2 - G(x)+1=x\left(\sum_{n=0}^{\infty}C_nx^n\right)^2-\sum_{n=0}^{\infty}C_nx^n+1$$ $$=\left(\sum_{n=0}^{\infty}C_nx^n\right)\left(\sum_{n=0}^{\infty}C_nx^{n+1}-1\right)+1$$ $$=x\left(\sum_{n=0}^{\infty}C_nx^n\right)\left(\sum_{n=1}^{\infty}C_nx^n\right)+1$$

But I really don't know how to conclude that this thing is 0.

Besides that, let's assume just for a second that I was able to prove that $xG(x)^2 - G(x)+1=0$.

From the equation above, we get that




How do I know which is the right one?

Now, let's pretend again that I fully understood the problem until this point, and that I know why $G(x)=\dfrac{1-\sqrt{1-4x}}{2x}$, how can I conclude that $G(x)=\sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}x^n?$

Hints, solutions, everything here is welcome... Thanks!


$\def\fr#1#2{{\textstyle{\frac{#1}{#2}}}}$ Hints. To prove the equation for $G(x)$, start with $$G(x)^2=\Bigl(\sum_{k=0}^\infty C_kx^k\Bigr)^2 =\sum_{n=1}^\infty\Bigl(\sum_{k=0}^{n-1}C_kC_{n-1-k}\Bigr)x^{n-1}\ ;$$ the second equality is true because if $n\ge1$, then the coefficient of $x^{n-1}$ in the square of the sum is the coefficient of $x^0$ times the coefficient of $x^{n-1}$, plus the coefficient of $x^1$ times the coefficient of $x^{n-2}$, and so on. Now multiply both sides by $x$ and use the given recurrence.

Solving the quadratic gives two possible answers as you have noted. To choose the correct one, note that from the series we have $G(0)=C_0=1$. Now in the quadratic solutions you cannot take $x$ equal to $0$ because you have $x$ in the denominator; but you can take the limit as $x$ approaches $0$.

For the final part, use the binomial theorem to expand $\sqrt{1-4x}$. We have $$\sqrt{1-4x}=(1-4x)^{1/2}=\sum_{n=0}^\infty C(\fr{1}{2},n)(-4x)^n$$ and we evaluate the binomial coefficient starting thus: $$\eqalign{C(\fr{1}{2},n) &=\frac{\frac{1}{2}(-\frac{1}{2})(-\frac{3}{2})\cdots(\frac{3}{2}-n)}{n!}\cr &=\frac{(-1)^{n-1}}{2^n}\frac{(2n-3)\cdots3\times1}{n!}\cr &=\frac{(-1)^{n-1}}{2^n}\frac{(2n-3)\cdots3\times1}{n!} \frac{(2n-2)(2n-4)\cdots4\times2}{(2n-2)(2n-4)\cdots4\times2}\cr &=\frac{(-1)^{n-1}}{2^n}\frac{(2n-2)!}{n!\,2^{n-1}(n-1)!}\ .\cr}$$ See if you can take it from here.


You can tell that the minus sign is correct, since you know that $G(x)$ is a power series, and if you used the plus sign, the numerator would start $1+1+...$, so that $G(x)$ would have a term $\frac{1}{x}$. To see that $G(x) = \sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}x^n$, note that $$(1+x)^{1/2} = \sum_0^\infty \dbinom{1/2}{k}x^k.$$ Now, $\dbinom{1/2}{k} = (-1)^k2^{1-2k}\frac{1}{k}\dbinom{2k-2}{k-1}$ for $k>0$, as you can see by just expanding the series for the left-hand side and simplifying. Thus $$(1+x)^{1/2} = \dbinom{1/2}{0} + \sum_{k=1}^\infty \dbinom{1/2}{k}x^k = 1 + \sum_{k=1}^\infty (-1)^{k-1}2^{1-2k}\frac{1}{k}\dbinom{2k-2}{k-1}x^k.$$ Now replace $x$ by $-4x$ to get $$(1-4x)^{1/2} = 1 + \sum_{k=1}^\infty (-1)^{k-1}2^{1-2k}\frac{1}{k}\dbinom{2k-2}{k-1}(-1)^k2^{2k}x^k = 1 + \sum_{k=1}^\infty (-2)\frac{1}{k}\dbinom{2k-2}{k-1}x^k.$$ Thus $$(1-4x)^{1/2}-1 = \sum_{k=1}^\infty (-2)\frac{1}{k}\dbinom{2k-2}{k-1}x^k = \sum_{k=0}^\infty (-1)\frac{1}{k+1}\dbinom{2k}{k}x^k.$$ Now multiply through by $-\frac{1}{2}$ to get $$\frac{1-\sqrt{1-4x}}{2} = \sum_{k=0}^\infty \frac{1}{k+1}\dbinom{2k}{k}x^k.$$


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.