# Solving Simple Recursive Equations

For recursive equations of the form $au_{n+2}=bu_{n+1}+cu_n$ I read that the trick is to let $u_n=\lambda^n$ for some $\lambda$ and then find an appropriate $\lambda$ that fits the initial conditions. However, what if the solutions to the resultant quadratic are repeated roots? For example, $u_{n+2}=2u_{n+1}-u_n$ leads to $\lambda^2-2\lambda+1=0$ or $\lambda=1$.

Also, is there are a generalisation of this trick? What if we have, say, $au_{n+2}=bu_{n+1}+cu_n+1$ or $au_{n+2}=bu_{n+1}+cu_n+f(n)$?

-
If there is a repeated root $\lambda$ then the general solution is $u_n = (a+bn)\lambda^n$ for $a$, $b$ constant. –  Chris Taylor Jan 18 '12 at 15:11
@Inquirer I think you mean $f(n)$ not $f(x)$. –  aelguindy Jan 18 '12 at 15:44

As Chris Taylor mentions, when you have repeated roots, the solution is just $(a_0 + a_1 n + a_2 n^{2} + .. + a_{k-1}n^{k-1}) \lambda^{n}$ if $\lambda$ is a root repeated $k$ times. As pointed out in the comments below, it is clearer and more correct to say that every root (of multiplicity $k$) gets multiplied by a polynomial of order $k - 1$. The general solution is a sum over all (distinct) roots multiplied by the corresponding polynomial.

The generalisation you ask for is as follows. You solve the equation ignoring the "non-homogeneous" terms (these include the constants and any $f(n)$. Then, you find a particular solution by the method of undetermined coefficients. The general solution is the sum of both. The method is described here in details.

For non-constant coefficients, I don't think there is a universal techniques but many classes can be solved via "generalized hypergeometric series", see the links. As for non-linear recurrences, there's no general technique.

-
Since wikipedia is down, you can view the links temporarily from the Google cache. First link (scroll to "Solving non-homogeneous recurrence relations") and second link. –  aelguindy Jan 18 '12 at 15:50
You can also append '?banner=none' (without quotes) to the URL, or disable javascript, or hit Esc before the blackout loads. –  Brian M. Scott Jan 18 '12 at 15:54
@BrianM.Scott Great hint! Thanks. –  aelguindy Jan 18 '12 at 15:55
I don't see how you deduce that the solution is $(a_0 + a_1 n + a_2 n^{2} + .. + a_{k-1}n^{k-1}) \lambda^{n}$ - could you show it? In fact, I am not sure why it even obeys the recursive equation - I must be missing something. –  user23178 Jan 19 '12 at 14:35
This solution is odd: since it involves $n^{k-1}$, you must be considering recursions of every order. But as soon as the order of the recursion is at least $3$, each root $\lambda$ has its own multiplicity. Hence the general solution is not what you write, but rather, a sum over the roots $\lambda$ of $P_\lambda(n)\lambda^n$ where each $P_\lambda$ is a polynomial whose degree is at most the multiplicity of $\lambda$ minus $1$. Note that this does not apply to @Chris's comment, which deals with recursions of order $2$. (Inquirer's trouble in the last comment above might be related to this.) –  Did Jan 29 '12 at 11:28

You can rewrite the equation $au_{n+2} = bu_{n+1}+cu_n$ as : $$L(u) = 0$$ where $$L(x) = bx_{n+1}+cx_n - ax_{n+2}$$ It'a obvious that $L$ is linear , so the equation $$L(u) = 0$$ is equivalent of finding the kernel of a linear transformation: we already know that this is is a vector space.

Let's try to find a basis: Any idea? Let's try a sequence of the form $\lambda^n$. Then we prove that good $\lambda$ are solutions of the polynomial above. We finally prove that $\lambda_1^n$ and $\lambda_2^n$ are a basis of the kernel space of $L$. That means the kernel dimension is 2 and all solutions of the equation are linear combination of the basis....

We can extrapolate to more complicated cases :

• kernel's dimension is equal (in most case) to the degree of the equation, so solutions are a linear combination of a basis which is built from solutions from the polynomial
• when your equation is $L(u)=c$ or $L(u)=f$, it becomes an affine equation : you solve the homogeneous equation, then you add a particular solution.

Note : This is the axactly same reasoning used with a differential equation like $ay'' + by' + cy = 0$. Thanks to linear algebra... ;-)

-

Use generating functions. Define $U(z) = \sum_{n \ge 0} u_n z^n$, multiply your recurrence by $z^n$ and add over $n \ge 0$ to get: $$a \frac{U(z) - u_0 - u_1 z}{z^2} = b \frac{U(z) - u_0}{z} + c U(z)$$ This is just a linear equation in $U(z)$, which will give a fraction in polynomials in $z$ when solved. Split into partial fractions (yes, they have uses outside integral calculus). This will give either: $$U(z) = \frac{a_1}{1 - r_1 z} + \frac{a_2}{1 - r_2 z}$$ which is just two geometric series: $$u_n = a_1 r_1^n + a_2 r_2^n$$ or terms of the form $$\frac{a}{(1 - r z)^m}$$ For the last type use the binomial theorem: $$(1 - \alpha)^{-m} = \sum_{n \ge 0} \binom{-m}{n} \alpha^n = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} \alpha^n$$ Note that: $$\binom{n + m - 1}{m - 1} = \frac{(n + m - 1) (n+ m - 2) \ldots (n + 1)}{(m - 1)!}$$ is just a $m - 1$-th degree polynomial in $n$.

-