Linear Recurrence Problem

Question

$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?

Answer 1

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$.

Answer 2

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.