solving linear recurrence - general solution confusion I've been trying to get my head around this for days. I understand what is going on with the calculation of a linear recurrence and I also understand how the characteristic is obtained.
What is confusion me is the general solution.
The general solution to the recurrence $at(n) + bt(n-1) ct(n-2) = 0$
For a unique root $r$, the general solution is: $t(n) = (A + Bn)  r^n$. For two distinct roots $r_1$ and $r_2$, the general solution is: $t(n) = Ar_1^n + Br_2^n$
What are $A$ and $B$? What do they represent in the linear recurrence and in the general solution
I just can't see it and I need to get it so I can start my discrete math assignment ...
Thanks heaps in advance :)
 A: $A$ and $B$ are related to the initial conditions of the linear recurrence.  To completely solve a linear recurrence of the form: $$at_n+bt_{n-1}+ct_{n-2}=0$$you need $a,b,c$, and also $t_0,t_1$, where the sequence starts. Given initial conditions, you can find a unique $A$ and $B$ that will give an exact solution.
A: A nice way of looking at this is using the techniques in Wilf's "generatingfunctionology" (2nd edition if free on the 'net).
Start with:
$$
u_{n + 2} + a u_{n + 1} + b u_n = c_n
$$
and starting conditoons $a_0$, $a_1$.
Define generating functions $U(z) = \sum_{n \ge 0} u_n z^n$ and $C(z) = \sum_{n \ge 0} c_n z^n$. You'll have to get $C(z)$ somehow.
Multiply the recurrence by $z^n$ and add for $n \ge 0$, identifying the resulting sums gives:
$$
\frac{U(z) - a_0 - a_1 z}{z^2} + a \frac{U(z) - a_0}{z} + b U(z) = C(z)
$$
Solve for $U(z)$, and split in partial fractions. This will very often give terms of the forms:
$$
\frac{1}{(1 - \alpha z)^m}
  = \sum_{n \ge 0} \binom{-m}{n} (-\alpha)^n z^n
  = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} \alpha^n z^n
$$
Here $\binom{n + m - 1}{m - 1}$ is just a $m - 1$-degree polynomial in $n$:
$$
\binom{n + m - 1}{m - 1}
  = \frac{(n + m - 1) (n + m - 2) \ldots (n + 1)}{(m - 1)!}
$$
You get $u_n$ by picking the coefficient of $z^n$ en each of the sums.
There definitely is a relation between the coefficients in $u_n$, but there isn't any simple formula.
