Closed-form expression with a Matrix

Question

I am looking for a closed-form expression for $f_n$.

Let $f_0 = 0, f_1 = 1, f_{n+1} = 4f_n -4f_{n-1} , n\geq 1$

$\begin{pmatrix} f_n \\ f_{n+1}\end{pmatrix} = A \cdot \begin{pmatrix} f_{n-1} \\ f_n\end{pmatrix}$

It follows that $A = \begin{pmatrix} 0 & 1\\ -4 & 4\end{pmatrix}$

Then we have

$\begin{pmatrix} f_n \\ f_{n+1}\end{pmatrix} = A^{n-1} \cdot \begin{pmatrix} f_{1} \\ f_0\end{pmatrix} = A^{n-1} \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix}$

Now i dont know how to continue

Answer 1

This is an approach that avoids diagonalization of $A$ in standard approach.
We will derive same answer by manipulating the powers of $A$ algebraically.

The characteristic polynomial for $A$ is given by

$$\chi_A(x) = \det(xI_2 - A) = \begin{vmatrix}x & -1\\-4 & x-4\end{vmatrix} = (x-2)^2 $$ By Cayley-Hamilition theorem, $(A-2I_2)^2 = 0$. For all $n > 0$, Binomial theorem tell us

$$\begin{align}A^n &= (2I_2 + (A-2I_2))^n \\ &= \sum_{k=0}^n \binom{n}{k}(2I_2)^{n-k} (A-2I_2)^k = \sum_{k=0}^1 \binom{n}{k}(2I_2)^{n-k} (A-2I_2)^k\\ &= 2^n I_k + n2^{n-1} (A-2I_2) = 2^n(1-n)I_2 + n2^{n-1}A \end{align} $$ This implies $$\begin{bmatrix}f_n\\f_{n+1}\end{bmatrix} = A^n \begin{bmatrix}f_0\\f_{1}\end{bmatrix} = 2^n(1-n) \begin{bmatrix}f_0\\f_{1}\end{bmatrix} + n2^{n-1} \begin{bmatrix}f_1\\f_{2}\end{bmatrix}$$ Compare the first entry on both sides, we obtain $$f_n = 2^n(1-n) f_0 + n2^{n-1} f_1 \quad\implies\quad f_n = n2^{n-1}$$

Answer 2

$$ A= T^{-1}DT= \begin{pmatrix} 0.98 & 0.20 \\ -0.64 & 0.77 \end{pmatrix}^{-1}\begin{pmatrix} 0.83 & 0 \\ 0 & -4.83\ \end{pmatrix}\begin{pmatrix} 0.98 & 0.20 \\ -0.64 & 0.77 \end{pmatrix}\\ f_n = \begin{pmatrix} 0.87 & 0.72 \\ -0.23 & 1.11 \end{pmatrix}\begin{pmatrix} 0.83^{n-1} & 0 \\ 0 & (-4.83)^{n-1} \end{pmatrix}\begin{pmatrix} 0.98 \\ -0.64 \end{pmatrix} $$