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.

  • 1
    $\begingroup$ oeis.org/A005773 $\endgroup$
    – RobPratt
    Sep 19, 2022 at 18:09
  • 2
    $\begingroup$ I recommend deriving the generating function from the recurrence relation. $\endgroup$
    – RobPratt
    Sep 19, 2022 at 18:15

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .