Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
(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
3  
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
add comment

4 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
Thank you very much for your explanation. I got it right. –  zneak Aug 1 '11 at 19:49
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.