Linear Difference Equations
Definition 1. Define a sequence $\{ X_n \in \mathbb{R}^k \mid n \ge 0 \}$ by a matrix equation $$X_n = A X_{n-1}, \quad n \ge 1, \quad \text{with an arbitrary } k \times k \text{ square matrix } A.$$ Such an equation $X_n = A X_{n-1}, n \ge 1$ is called a linear difference equation (LdE) of order $k$.
A solution to an LdE $X_n = A X_{n-1}$ is a sequence $\{ X_n \in \mathbb{R}^k \mid n \ge 0 \}$ that satisfies the equation.
Remark. Since $X_n = A^nX_0$ is a unique solution with initial value $X_0$, solving an LdE is reduced to a computation of $A^n$ if the initial value $X_0$ is given. Hence, every LdE $X_n = AX_{n-1}$ has a solution. (In fact, infinitely many depending on the choice of $X_0$.)
Theorem 1
Theorem 1. Let $X_n = AX_{n-1}, n \ge 1$ be an LdE, where $A \in M_{k \times k}(\mathbb{R})$.
(i) If $\lambda$ is an eigenvalue of $A$ belonging to a vector $v \in \mathbb{R}^k$, then $X_n = \lambda^n v$ is a solution to $X_n = AX_{n-1}$.
(ii) The set of all solutions to the LdE $X_n = AX_{n-1}$ forms a $k-$dimensional vector space.
(iii) The set of solutions to an LRR of order $k$, $$x_n = a_1x_{n-1} + \cdots + a_kx_{n-k}, \quad n \ge k$$ with $a_k \neq 0$, is a $k-$dimensional vector space.
Proof.
(i) Note that $$X_n = \lambda^n v = \lambda^{n-1} (\lambda v) = \lambda^{n-1} A v = A (\lambda^{n-1} v) = A X_{n-1}.$$ Thus $X_n = \lambda^n v$ is a solution to the LdE.
(ii) Clearly, a sum of two solutions and any scalar multiplication of a solution are also solutions to the LdE. By regarding the zero sequence $\mathbf{0}$ as the zero vector, the set of solutions forms a vector space.
Let $\{ e_1, ..., e_k \}$ be the standard ordered basis for $\mathbb{R}^k$. For each $e_i$, there exists the unique solution $S_i = \{ X_n = A^n e_i \in \mathbb{R}^k \mid n \ge 0 \}$ to the LdE with initial value $e_i$. Suppose that $c_1 S_1 + \cdots + c_k S_k = \mathbf{0}$. Then $c_1 e_1 + \cdots c_k e_k = \mathbf{0}$, which implies that $c_1 = \cdots = c_k = 0$. Thus $\{ S_1, ..., S_k \}$ is linearly independent. Since $\{ e_1, ..., e_k \}$ generates any initial value, $\{ S_1, ..., S_k \}$ is a basis for the vector space of all solutions to the LdE. Hence the set of all solutions to the LdE is a $k-$dimensional vector space.
(iii) It is the corollary of (ii). $\blacksquare$
Corollary
Corollary. Let $A$ be a $k \times k$ diagonalizable matrix with $k$ linearly independent eigenvectors $v_1, \ldots,v_k$ belonging to the eigenvalues $\lambda_1, \lambda_2, \ldots, \lambda_k$, respectively. Then, a general solution to an LdE $X_n = AX_{n-1}$ is \[ X_n = c_1 \lambda_1^n v_1 + \cdots + c_k \lambda_k^n v_k \quad \text{with constants } c_i\text{'s.} \] If an initial vector $X_0$ is given, the constants $c_1, c_2, \ldots, c_k$ can be determined for a particular solution.
Theorem 2
Theorem 2. For any given LRR \[ x_n = a_1 x_{n-1} + a_2 x_{n-2} + \cdots + a_k x_{n-k}, \quad n \ge k \] with nonzero $a_k \neq 0$, if the associated companion matrix $A$ has $t$ distinct eigenvalues $\lambda_1, \lambda_2, \ldots, \lambda_t$ with multiplicities $m_1, m_2, \ldots, m_t$, respectively, where $m_1 + m_2 + \cdots + m_t = k$, then \[ \left\{ \{\lambda_i^n\}, \{n\lambda_i^n\}, \ldots, \{n^{m_i-1}\lambda_i^n\} \mid i = 1, 2, \ldots, t \right\} \] forms a basis for the set of solutions, and a general solution is a linear combination of these solutions with constants $c_i$'s.
Proof. Note that the characteristic polynomial of $A$ is $$f(t) = (-1)^k(t^k - a_1 t^{k-1} - \cdots - a_{k-1} t - a_k).$$ Let $\lambda_i$ be an eigenvalue of $A$ with multiplicity $m_i > 1$. Then we have $$f(t) = (t - \lambda_i)^{m_i} g(t)$$ where $g(\lambda_i) \neq 0$. Hence, $$f(\lambda_i) = f'(\lambda_i) = \cdots = f^{(m_i-1)}(\lambda_i) = 0.$$ Since $f(\lambda_i) = 0$, we have $$\lambda_i^{n-k} f(\lambda_i) = (-1)^k (\lambda_i^n - a_1 \lambda_i^{n-1} - \cdots - a_{k-1} \lambda_i^{n-k+1} - a_k \lambda_i^{n-k}) = 0, \forall n \ge k,$$ so that $\{ x_n \} = \{ \lambda_i^n \}$ is a solution to the given LRR.
Since $f(\lambda_i) = f'(\lambda_i) = 0$, we have $(\lambda_i^{n-k}f(\lambda_i))' = 0$ for $n \ge k$. Then $$\lambda_i(\lambda_i^{n-k}f(\lambda_i))' = (-1)^k(n \lambda_i^n - a_1(n-1)\lambda_i^{n-1} - \cdots \\ - a_{k-1}(n-k+1)\lambda_i^{n-k+1} - a_k(n-k)\lambda_i^{n-k}) = 0, \forall n \ge k,$$ so that $\{ x_n \} = \{ n \lambda_i^n \}$ is a solution to the LRR.
Similarly, since $f(\lambda_i) = f'(\lambda_i) = f''(\lambda_i) = 0$, we obtain a solution $\{ x_n \} = \{ n^2 \lambda_i^n \}$ to the LRR.
By repeating it, we obtain the linearly independent solutions $$\{ \lambda_i^n \}, \{ n \lambda_i^n \}, \cdots, \{ n^{m_i-1} \lambda_i^n \}$$ to the LRR.
By Theorem 1 (iii), the set of solutions to the LRR is a $k-$dimensional vector space. Since $$\left\{ \{\lambda_i^n\}, \{n\lambda_i^n\}, \ldots, \{n^{m_i-1}\lambda_i^n\} \mid i = 1, 2, \ldots, t \right\}$$ is clearly linearly independent, this set forms a basis for the set of solutions to the LRR. $\blacksquare$