Finding the generating function of a sequence $(f(n))_{n\geq 0}$

46 Views Asked by At

Let $f(n)$ be a function on the non-negative integers defined recursively in the form $$f(n)=af(n-1)+bf(n-2)+cf(n-2)+p(n)\alpha^n,$$ where the $a,b,c,\alpha \in\mathbb{C}$ and $p$ is a polynomial with complex coefficients.

Show that the generating function for the sequence $f(0),f(1),f(2),\dots$ will be a quotient of polynomials in $x$, and hence there is a closed form expression for $f(n)$.

1

There are 1 best solutions below

0
On

Let $F(x)=\sum_{n\geq 0}f(n)x^n$ be such generating function. Then after multiplying your equation by $x^n$ and taking the sum for $n\geq 2$, we obtain $$\sum_{n\geq 2}f(n)x^n=ax\sum_{n\geq 2}f(n-1)x^{n-1}+(b+c)x^2\sum_{n\geq 2}f(n-2)x^{n-2}+\sum_{n\geq 2}p(n)(\alpha x)^n.$$ That is $$F(x)-(f(1)x+f(0))=ax(F(x)-f(0))+(b+c)x^2F(x)+G(x)$$ where $G$ is some rational function (why?).

Can you take it form here?