Generating Functions · Linear Recurrence Relations

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Rewrite this relation in the following form: \[C(n)-3C(n-2)-2C(n-3)=0 \ .\]

Now consider the generating function \(\mathcal{C}(x)=\sum_{n \in \mathbb{Z}_{\ge 0}}C(n)x^{n}\) and write the sum, where the equation above zeros everything out.

We get \[\mathcal{C}(x)(1-3x^{2}-2x^{3})=5+5x-3x^{2} \ .\] Therefore, \[\mathcal{C}(x)=\frac{5+5x-3x^2}{1-3x^2-2x^3}\ .\] Decompose this rational function into partial fractions: \[\frac{5+5x-3x^2}{1-3x^2-2x^3}=-\frac{3}{2x-1}+\frac{3}{x+1}-\frac{1}{(x+1)^2}\]

from sympy import apart
from sympy.abc import x

frac = (5 + 5 * x - 3 * x ** 2) / (1 - 3 * x ** 2 - 2 * x ** 3)
print(apart(frac))

-3/(2*x - 1) + 3/(x + 1) - 1/(x + 1)**2

Then, \[\begin{align*}[x^{n}]\frac{1}{1-2x}&=2^{n}\ ,\\\frac{1}{x+1}&=(-1)^{n}\ ,\\\frac{1}{(1+x)^2}&=(-1)^{n}\binom{n+1}{n}=(-1)^{n}(n+1)\ .\end{align*}\] Hence, \[C(n)=3\cdot2^{n}+3(-1)^{n}-(n+1)(-1)^{n}=3\cdot 2^{n}-(-1)^{n}(n-2) \ .\]