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

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?

-
(1) The characteristic equation of $c_{n}=3c_{n−1}−2c_{n−2}$ should be only $x^2 = 3x-2$; in particular, the degree of the polynomial does not depend on $n$. (2) Before reading any other answer/hint, I recommend hand-solving the recurrence $a_{n} = 2a_{n-1} - a_{n-2}$ with base conditions $a_0 = 3$ and $a_1 = 5$. (Notice that the characteristic equation has one repeated root at $1$.) Do you see a pattern in the solution? Can you guess the solution and prove it using, say, induction? Can you now make any guesses about your question? – Srivatsan Aug 1 '11 at 4:17
Maybe in a DE course you bumped into the same issue. The solution is the same. – André Nicolas Aug 1 '11 at 4:32
Several solutions and hints have already been given. See also this section of the Wikipedia article, this answer and this one. The key is, as robjohn noted, that the difference operator $(\Delta-r)^k$ annihilates each $n^jr^n$ for $j<k$, which you can prove by induction over $k$. – joriki Aug 1 '11 at 4:47

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.

-
Thank you very much for your explanation. I got it right. – zneak Aug 1 '11 at 19:49

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$.

-
Thank you! I can't pick more than one accepted answer, but I upvoted you anyways. – zneak Aug 1 '11 at 19:49
@zneak: Thanks for the upvote! My edits put my answer later, so I understand. – robjohn Aug 1 '11 at 23:09

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ You can always insert a parameter $\ds{\epsilon}$ to 'remove' the equality of the roots. At the end, take a proper limit to restore the original recurrence. In order to illustrate the method I'll solve the simple example $$a_{n + 1} - 2a_{n} + a_{n - 1} = 0\qquad\mbox{with}\qquad a_{0} = 0\,,\quad a_{1} = 1$$ The solution is, of course, $\color{#66f}{\LARGE \ds{a_{n} = n}}$ and the 'characteristic equation' has the double root equal to one.

Instead, I'll solve $\ds{a_{n + 1} - 2a_{n} + \epsilon a_{n - 1} = 0}$. The 'characteristic equation' has roots $\ds{r_{\pm} = 1 \pm \underbrace{\root{1 - \epsilon^{2}}}_{\ds{\equiv \delta}}}$ \begin{align} a_{n}&= Ar_{-}^{n} + Br_{+}^{n}\quad\imp\quad A + B = 0\,,\quad Ar_{-} + Br_{+} = 1 \quad\imp\quad \left\lbrace\begin{array}{rcl} A & = & {1 \over r_{-} - r_{+}} \\ B & = & -A \end{array}\right. \\[3mm] a_{n} &={r_{-}^{n} - r_{+}^{n} \over r_{-} - r_{+}} \end{align}

The limit $\ds{\epsilon \to 1}$ yields: $$\lim_{\epsilon \to 1}{r_{-}^{n} - r_{+}^{n} \over r_{-} - r_{+}} =\lim_{\delta \to 0}{\pars{1 - \delta}^{n} - \pars{1 + \delta}^{n} \over -2\delta} =\lim_{\delta \to 0} {n\pars{1 - \delta}^{n - 1}\pars{-1} - n\pars{1 + \delta}^{n - 1} \over -2} =\color{#66f}{\LARGE n}$$

-

Use generating function directly: define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence with no subtractions in indices: $$a_{n + 3} = 9 a_{n + 2} - 15 a_{n + 1} - 25 a_n$$ Multiply by $z^n$ and sum over $n \ge 0$, recognize: $$\sum_{n \ge 0} a_{n + k} z^n = \frac{A(z) - a_0 - a_1 z - \ldots - a_{k - 1} z^{k + 1}}{z^k}$$ to get: $$\frac{A(z) - 2 z + z^2}{z^3} = 9 \frac{A(z) - 2 z}{z^2} - 15 \frac{A(z)}{z} - 25 A(z)$$ Written as partial fractions: $$A(z) = \frac{53}{60 (1 - 5 z)} - \frac{3}{10 (1 - 5 z)^2} - \frac{7}{12 (1 + z)}$$ The generalized binomial theorem lets you read off coefficients: \begin{align} a_n &= \frac{53}{60} \cdot 5^n - \frac{3}{10} \binom{-2}{n} (-5)^n - \frac{7}{12} \cdot (-1)^n \\ &= \frac{53}{60} \cdot 5^n - \frac{3}{10} \binom{n + 2 - 1}{2 - 1} \cdot 5^n - \frac{7}{12} \cdot (-1)^n \\ &= \frac{(35 - 18 n) \cdot 5^n - 35 \cdot (-1)^n}{60} \end{align} Repeat roots give terms including $\binom{-m}{n} = \binom{n + m - 1}{m - 1}$, which is just a polynomial of degree $m - 1$ in $n$.

-