Linear Recurrence Problem $f(0)=3, f(1)=1, f(n)=4f({n-1})+21f({n-2})$
Thought linear recurrence problems usually have subsets of things, and this seems like a new type for me.
Can anyone help me out with hints?
 A: First, solve the characteristic equation:
$$q^2 = 4q + 21$$
$$q^2-4q-21 = (q-7)(q+3)$$
So our solution is of the form
$$f(n) = c_17^n + c_2 (-3)^n$$
Use the given values to calculate the constants
$$3 = c_1+c_2$$
$$1 = 7c_1 - 3c_2$$
$$\Rightarrow c_1 = 1, c_2 = 2$$
$$f(n) = 7^n + 2(-3)^n$$

At $n=2$, the closed form gives
$$49+18 = 67$$
And the recurrence gives
$$4(1) + 21(3) = 67$$
So it looks like the answer is correct.
A: Outline: 
You can the general linear algebra approach for this type of recurrence relations. Consider the sequence of $2$-dimensional vectors
$$
x_n \stackrel{\rm def}{=} \begin{pmatrix}
f(n) \\
f(n-1)
\end{pmatrix}
$$
for $n\geq 1$, and rewrite your recurrence relation
$$
x_n = \begin{pmatrix}
4f(n-1) + 21f(n-2) \\
f(n-1)
\end{pmatrix} = 
\begin{pmatrix}
4 & 21\\
1 & 0
\end{pmatrix}\begin{pmatrix}
f(n-1) \\
f(n-2)
\end{pmatrix} = 
M x_{n-1}
$$
for $M \stackrel{\rm def}{=} 
\begin{pmatrix}
4 & 21\\
1 & 0
\end{pmatrix}$, with $x_1 = \begin{pmatrix}
1\\
3
\end{pmatrix}$. 
Then, try to diagonalize $M$, i.e. to get $P$ invertible and $\Delta$ diagonal such that $M=P^{-1}\Delta P$. From there, it is straightforward to see that 
$$
x_{n} = M^{n-1} x_1 = P^{-1}\Delta^{n-1} P x_1
$$
when $\Delta^{n-1}$ is very easy to compute (you know $\Delta$, and it's diagonal), you know $P$, and you know $x_1$. This will give $x_n$, for general $n$.
