Extracting Coefficients of Generating Function

Question

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.

Answer 1

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}. $$