0
$\begingroup$

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)$?

  • 0
    @Inquirer I think you mean $f(n)$ not $f(x)$.2012-01-18

3 Answers 3

2

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.

  • 0
    @DidierPiau Yes, that is what I meant, each specific solution (of some root) gets multiplied by a polynomial of degree multiplicity minus one. The way I write it is not very correct. Thanks for catching that!2012-01-29
1

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... ;-)

0

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