Using a generating function to determine $a_n$ from a general second order recurrence relation

Question

Suppose you have a second order recurrence relation with constant coefficients defined as follows: \begin{cases} a_n = A a_{n-1} + B a_{n-2}, n = 2, 3, ...\\ a_0, a_1 \text{ are given initial conditions} \end{cases}

I want to use the generating function $f(x) = \sum_{n=0}^{\infty} a_n x^n$ to determine $a_n$.

So far I have $f(x) = \cfrac{(a_1 -A a_o)x + a_o}{1 - Ax - Bx^2}$, but I think I am not approaching this the right way.

Answer 1

Hint: expand the generating function in partial fractions. You'll want to consider two cases, depending on whether or not the denominator has distinct roots.

Answer 2

$a_n-Aa_{n-1}-Ba_{n-2}=0$ is homogeneous recursive equation and if $\alpha \,,\beta$ be the roots of equation $x^2-Ax-B=0$ then $$a_n={\alpha}^n+{\beta}^n$$ Hence for given question $$a_n=(\cfrac{-B+\sqrt {A^2+4B}}{2})^n+(\cfrac{-B-\sqrt{A^2+4B}}{2})^n$$

For more details you can check this link also for non homogeneous recursive equation also. https://www.mathsdiscussion.com/discussion-forum/topic/recursive-equation/?part=1#postid-127