How do I resolve a recurrence relation when the characteristic equation has fewer roots than terms?

Question

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?

Answer 1

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.

Answer 2

Factor the characteristic polynomial to get $$ x^3-9x^2+15x+25=(x+1)(x-5)^2 $$ The $x+1$ factor requires a term of the form $a(-1)^k$, but the $(x-5)^2$ term requires $(b+ck)5^k$. This is because both $5^k$ and $k\:5^k$ are annihilated by the difference operator $(\Delta-5)^2$. Now, just find $a$, $b$, and $c$ to fit your initial data.

For factors of $(x-a)^n$, use $(b_0+b_1 k+b_2 k^2+...+b_{n-1}k^{n-1})a^k$ since this is annihilated by $(\Delta-a)^n$.