I know how to solve "simple" recurrence relations. For instance, say you have:
$$c_0 = 20$$
$$c_1 = 30$$
$$c_n = 3 c_{n-1} – 2 c_{n-2}$$
We can write the characteristic equation as:
$$3x^{n-1} – 2x^{n-2} = x^n$$
Solving this with $n=2$, we get $x = 1$ or $x = 2$. This lets us write the relation $c_n = \alpha_1 1^n + \alpha_2 2^n$, and we can solve for $\alpha_1$ and $\alpha_2$ with the initial states $c_0$ and $c_1$.
However, this depends on the fact that $3x^{n-1} – 2x^{n-2} = x^n$ has two roots.
Now, I'm stuck on another problem where the characteristic equation has fewer roots than terms.
Say I have this recurrence relation instead:
$$a_0 = 0$$
$$a_1 = 2$$
$$a_2 = −1$$
$$a_n = 9a_{n-1} – 15a_{n-2} – 25a_{n-3}$$
The characteristic equation would be:
$$9x^{n-1} – 15x^{n-2} – 25x^{n-3} = x^n$$
However, solving with $n=3$, we only get two roots: $x=-1$ or $x=5$. There are not enough roots to write a relation in the form of $a_n = \alpha_1 r_1^n + \alpha_2r_2^n + \alpha_3r_3^n$. How do I proceed?
Best Answer
The characteristic equation is actually $x^3-9x^2+15x+25 = 0$; it doesn’t depend on $n$. After factoring this becomes $(x+1)(x-5)^2 = 0$, with a double root at $x=5$. In this case the general solution has the form $a_n = \alpha_1(-1)^n + \alpha_2 \cdot 5^n + \alpha_3n \cdot 5^n$, and you can use the known values of $a_0,a_1,a_2$ to solve for $\alpha_1,\alpha_2,\alpha_3$.
More generally, if $r$ is a root of the characteristic equation of multiplicity $m$, it gives rise to these $m$ terms in the general solution:$$\alpha_1r^n + \alpha_2nr^n + \alpha_3n^2 r^n + \dots + \alpha_m n^{m-1}r^n.$$Thus, you will always have as many terms as the degree of the characteristic equation.