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)$?
 A: 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.
A: 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... ;-)
A: 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$.
