<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] I did not check your work, so I’ll outline what you need to do to finish. You have something of the form
$$A(x)=\frac{a}{1-x}+\frac{b}{5-x}+\frac{c}{(1-x)^2}=\frac{a}{1-x}+\frac{b/5}{1-\frac{x}5}+\frac{c}{(1-x)^2}\;.$$
Expand these three terms into power series:
$$\begin{align*}
A(x)&=a\sum_{n\ge 0}x^n+\frac{b}5\sum_{n\ge 0}\left(\frac{x}5\right)^n+c\sum_{n\ge 0}(n+1)x^n\\\\
&=\sum_{n\ge 0}\left(a+\frac{b}{5^{n+1}}+c(n+1)\right)x^n\;.
\end{align*}$$
Now you can read off the coefficient of $x^n$.
Added: I’ve now had a chance to check your work, and it appears to be a bit off. I’ll use my preferred approach, which begins by assuming that $a_n=0$ for all $n<0$. Then the recurrence can be written
$$a_n=6a_{n-1}-5a_{n-2}+1-[n=0]+4[n=1]\;,$$
for all $n\ge 0$, where the last two terms contain Iverson brackets and are added to make the recurrence give the correct values to $a_0$ and $a_1$. Now multiply through by $x^n$ and sum over $n\ge 0$:
$$\begin{align*}
\sum_{n\ge 0}a_nx^n&=\sum_{n\ge 0}\Big(6a_{n-1}-5a_{n-2}+1-[n=0]+4[n=1]\Big)x^n\\\\
&=6x\sum_{n\ge 0}a_{n-1}x^{n-1}-5x^2\sum_{n\ge 0}a_{n-2}x^{n-2}+\sum_{n\ge 0}x^n-1+4x\;.
\end{align*}$$
Since $A(x)=\sum_{n\ge 0}a_nx^n=\sum_{n\ge 0}a_{n-1}x^{n-1}=\sum_{n\ge 0}a_{n-2}x^{n-2}$ (remember the blanket assumption that $a_n=0$ for $n<0$), we have
$$A(x)=6xA(x)-5x^2A(x)+\frac1{1-x}-1+4x\;,$$
and hence
$$A(x)=\frac1{(1-x)^2(5-x)}+\frac{4x-1}{(1-x)(5-x)}\;.$$
I’ll leave the partial fraction decomposition to you, at least for now.
</s>