I am looking at various recurrence relations of the form:
$x_{n+2} + bx_{n+1} +cx_{n} = f(n)$
In the book I use, I have been given an algorithm on how to solve these kinds of recurrence relations when $f(n)$ is a polynomial $p(n)$, of the form $a^n p(n)$ and when it's of the form $b^n \left[ Asin(an)+ Bcos(an) \right]$. Also, I am shown that the algorithm gives me a valid answer. However, I do not know how to deduce the algorithm myself.
So, if $f(n) = 0$, I have to expect a solution of the form $Ar^n$. So, I have to solve a quadratic equation (since $r^{n+2} + br^{n+1} +cr^ {n} = 0$). So, the two roots $r_1$ and $r_2$ gives me the solution $x_n = Ar_1^n + Br_2^n$. However, if there is only one root $r$, the solution suddenly takes the form $x_n= Ar^n + Bnr^n$. I do not know why.
Is generating functions the only way to try to understand these kinds of recurrence relations and why they have the solutions they do?
This question is specifically about three types of $f(n)$:
- When $f(n)$ is a polynomial $p(n)$
- When $f(n) = a^n p(n)$. Again, $p(n)$ is a polynomial, and $a \in \mathbb{R}$
- When $f(n) = b^n \left[ Asin(an)+ Bcos(an) \right]$ $a,b,A,B \in\mathbb{R}$