<s>[INST] Solving recurrence relation, $a_n=6a_{n-1} - 5a_{n-2} + 1$ I'm trying to solve this recurrence relation:
$$
a_n = \begin{cases} 
    0 & \mbox{for } n = 0 \\
    5 & \mbox{for } n = 1 \\
    6a_{n-1} - 5a_{n-2} + 1 & \mbox{for } n > 1
    \end{cases}
$$
I calculated generator function as:
$$
A = \frac{31x - 24x^2}{1 - 6x + 5x^2} + \frac{x^3}{(1-x)(1-6x+5x^2)} = 
\frac{31x - 24x^2}{(x-1)(x-5)} + \frac{x^3}{(1-x)(x-1)(x-5)}
$$
(I'm not sure if that's right)
and its partial fractions decomposition looks like:
$$
A = \left(\frac{-7}{4} \cdot \frac{1}{x-1} - \frac{445}{4} \cdot \frac{1}{x-5}\right) +
\left( \frac{39}{16} \cdot \frac{1}{x-5} + \frac{3}{4} \cdot \frac{1}{(x-1)^2} - \frac{375}{16} \cdot \frac{1}{x-5} \right)
$$
(again - I'm not sure if it's ok)
I'm stuck here... From solutions I know that I should get:
$$
a_n = \frac{-21}{16} - \frac{1}{4}n + \frac{21}{16}5^n
$$
but I have no idea how it's solved... I hope somebody can help me (I spend more than 3h trying to solve this myself...)
 [/INST] Use Wilf's technique from "generatingfunctionology". Define $A(z) = \sum_{n \ge 0} a_n z^n$, and write:
$$
a_{n + 2} = 6 a_{n + 1} - 5 a_n + 1 \qquad a_0 = 0, a_1 = 5
$$
Multiply by $z^n$ and add for $n \ge 0$, which gives:
$$
\frac{A(z) - a_0 - a_1 z}{z^2} = 6 \frac{A(z) - a_0}{z} - 5 A(z) + \frac{1}{1 - z}
$$
Solving for $A(z)$ gives:
$$
A(z) = \frac{5 z - 4 z^2}{1 - 7 z + 11 z^2 - 5 z^3}
     = \frac{21}{16} \cdot \frac{1}{1 - 5 z}
         - \frac{17}{16} \cdot \frac{1}{1 - z}
         - \frac{1}{4} \cdot \frac{1}{(1 - z)^2}
$$
Remember the expansions:
$$
(1 - u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} (-u)^k
             = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} u^k
$$
(the binomial coefficient is just an $m-1$-degree polynomial in $k$) and you are all set:
$$
a_n = \frac{21}{16} \cdot 5^n - \frac{17}{16} - \frac{1}{4} \binom{n + 1}{1}
    = \frac{21 \cdot 5^n - 4 n - 21}{16}
$$
Maxima's help with the algebra is gratefully acknowledged.
</s>