I stuck at the following problem:
Let $C_n$ be a sequence with the Following Ordinary Generating function:
$$\sum_{n=1}^{\infty} C_n x^n=\frac{1}{2}\sqrt{\frac{1+x}{1-3x}}-\frac{1}{2}.$$
The sequence $C_n$ satisfies in the recurrence relation
$$nC_n=2nC_{n-1}+3(n-2)C_{n-2}.$$
I find Combinatorial proof for this recurrence relation and proved it.
I have tried to prove this recurrence relation by extracting the coefficients of its generating function.
I tried as following:
The first, I writed
$$\sqrt{\frac{1+x}{1-3x}}=\frac{1+x}{\sqrt{(1+x)(1-3x)}}=\frac{1+x}{\sqrt{1-2x-3x^2}}$$
Then,
$$\frac{1}{\sqrt{(1-(2x+3x^2)}}=\sum_{n=0}^{\infty}{\frac{-1}{2}\choose n}(-1)^n(2x+3x^2)^n=\sum_{n=0}^{\infty}{\frac{-1}{2}\choose n}(-1)^n(2x)^n(1+\frac{3}{2}x)^n=\sum_{n=0}^{\infty}{\frac{-1}{2}\choose n}(-1)^n(2x)^n\sum_{\ell=0}^{n}{n\choose \ell}(\frac{3}{2}x)^{\ell}.$$
I could not continue it more. Could you please help me to extracting coefficients of this generating function to prove the above recurrence relation?
Thanks in advance.
Best Answer
We are given that
$$ y := \sum_{n=1}^\infty C_n x^n=\frac12\sqrt{\frac{1+x}{1-3x}}-\frac12. $$
Differentiate to get
$$ y' = \sum_{n=1}^\infty n C_{n}x^{n-1} = \frac1{(1-3x)^{3/2} \sqrt{1+x}}. $$
Verify that
$$ y'(1-2x-3x^2) = y'(1+x)(1-3x) = 1+2y. $$
Now extract the coefficients of both sides to get the recurrence
$$ nC_n=2nC_{n-1}+3(n-2)C_{n-2}. $$