<s>[INST] recurrence relation, linear, second order, homogeneous, constant coefficients, generating functions How to solve this by using the generating functions? What is the possible solution for this?
recurrence relation $$ a_n = 5a_{n-1} – 6a_{n-2}, n \ge 2,\text{ given }a_0 = 1, a_1 = 4.$$
Thanks.
 [/INST] $$
\begin{align}
a_n & = 5 a_{n-1} - 6 a_{n-2}\\
a_n - 3a_{n-1} & = 2 (a_{n-1} - 3 a_{n-2})
\end{align}
$$
Letting $T_n = a_n - 3a_{n-1}$ we get that $T_n = 2T_{n-1}$ and $T_1 = a_1 - 3a_0 = 1$. Hence, $$T_n = 2T_{n-1} = 2^2 T_{n-2} = \cdots = 2^{n-1} T_1 = 2^{n-1}$$
Hence,
$$
\begin{align}
a_n - 3a_{n-1} & = 2^{n-1}\\
a_{n-1} - 3a_{n-2} & = 2^{n-2}\\
a_{n-2} - 3a_{n-3} & = 2^{n-3}\\
\vdots \\
a_2 - 3a_1 & = 2
\end{align}
$$
Multiply the second equation by $3$, the third equation by $3^2$, and in general the $k^{th}$ equation by $3^{k-1}$ and add them up to get,
$$
\begin{align}
a_n - 3^{n-2} \times 3a_1 & = 2^{n-1} + 3 \times 2^{n-2} + 3^2 \times 2^{n-3} \cdots + 3^{n-2} \times 2\\
& = 2^{n-1} \times \left( 1 + \frac32 + \left(\frac32 \right)^2 + \cdots + \left( \frac32 \right)^{n-2} \right)\\
& = 2^{n-1} \left( \frac{\left(\frac32\right)^{n-1}-1}{\frac32-1} \right)\\
& = 2 \left( 3^{n-1} - 2^{n-1} \right)\\
a_n & = 2 \left( 3^{n-1} - 2^{n-1} \right) + 3^{n-1} a_1\\
 & = 6 \times 3^{n-1} - 2^n
\end{align}
$$
Hence, $$a_n = 2 \times 3^n - 2^n$$
</s>