# Extracting Coefficients of Generating Function

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?

• oeis.org/A005773 Sep 19, 2022 at 18:09
• I recommend deriving the generating function from the recurrence relation. Sep 19, 2022 at 18:15

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

• Elegant approach. (+1) Sep 20, 2022 at 5:02
• @Somos Thank you Somos. Is it possible proved it with extracting coefficients in summations of my answer? or extract closed fourmula for it!
– d.y
Sep 20, 2022 at 9:03
• @dy I doubt that you approach will work to verify the recurrence. As for closed formula, please consult A005773. Sep 20, 2022 at 12:19