5
$\begingroup$

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?

  • 0
    Several solutions and hints have already been given. See also [this section of the Wikipedia article](http://en.wikipedia.org/wiki/Recurrence_relation#Theorem), [this answer](http://math.stackexchange.com/questions/24963/how-to-solve-this-recurrence-relation/24966#24966) and [this one](http://math.stackexchange.com/questions/37157/recurrence-relation/37164#37164). The key is, as robjohn noted, that the difference operator $(\Delta-r)^k$ annihilates each $n^jr^n$ for j, which you can prove by induction over $k$.2011-08-01

4 Answers 4

1

$\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} $

7

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 $(S-5)^2$ (where $S$ is the shift operator: $Sa_n=a_{n+1}$). 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 $(S-a)^n$.

  • 0
    @KennethWorden: I fixed a typo. $(S-5)5^k=5^{k+1}-5^{k+1}=0$. Thus, $(S-5)$ annihilates $5^k$. $(S-5)k5^k=(k+1)5^{k+1}-k5^{k+1}=5^{k+1}$ so that $(S-5)^2k5^k=(S-5)5^{k+1}=5^{k+2}-5^{k+2}=0$. Thus, $(S-5)^2$ annihilates $k5^k$.2017-02-22
7

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.

  • 1
    Why do you multiply the exponential sequence of the root by increasing powers of n?2017-02-22
1

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