# Solve a Linear Recurrence Relation Using Vector Space Technique

## Problem 321

Let $V$ be a real vector space of all real sequences
$(a_i)_{i=1}^{\infty}=(a_1, a_2, \dots).$ Let $U$ be a subspace of $V$ defined by
$U=\{(a_i)_{i=1}^{\infty}\in V \mid a_{n+2}=2a_{n+1}+3a_{n} \text{ for } n=1, 2,\dots \}.$ Let $T$ be the linear transformation from $U$ to $U$ defined by
$T\big((a_1, a_2, \dots)\big)=(a_2, a_3, \dots).$

(a) Find the eigenvalues and eigenvectors of the linear transformation $T$.

(b) Use the result of (a), find a sequence $(a_i)_{i=1}^{\infty}$ satisfying $a_1=2, a_2=7$.

## Solution.

### (a) Find the eigenvalues and eigenvectors of the linear transformation $T$.

Note that each sequence $(a_i)_{i=1}^{\infty}$ in $U$ is determined by the first two numbers $a_1, a_2$ since the rests can be obtained from the linear recurrence relation $a_{n+2}=2a_{n+1}+3a_{n}$.
Thus, for example, we take $(a_1, a_2)=(1,0), (0, 1)$ and obtain a basis $B=\{\mathbf{u}_1, \mathbf{u}_2\}$ of $U$, where
\begin{align*}
\mathbf{u}_1 &=(1, 0, 3, 6, 21, \cdots )\\
\mathbf{u}_2 &=(0, 1, 2, 7, 20, \dots).
\end{align*}

We find the matrix $A$ of $T$ with respect to the basis $B$.
We have
\begin{align*}
T(\mathbf{u}_1)&=(0, 3, 6, 21, \cdots )=0 \mathbf{u}_1+3\mathbf{u}_2\\
T(\mathbf{u}_2) &=(1, 2, 7, 20, \dots)=\mathbf{u}_1+2\mathbf{u}_2.
\end{align*}

Thus, the matrix $A$ for $T$ is
$A=\begin{bmatrix} 0 & 1\\ 3 & 2 \end{bmatrix}.$

Then the eigenvalues of $T$ are eigenvalues of $A$.
The characteristic polynomial for $A$ is
\begin{align*}
p_A(t)=\det(A-tI)=t^2-2t-3=(t+1)(t-3).
\end{align*}
Thus the eigenvalues are $t=-1, 3$.

Let us find eigenvectors corresponding to $t=-1$.
We solve
$T\big((a_1, a_2, \dots)\big)=-(a_1, a_2, \dots),$ or equivalently,
$(a_2, a_3, \dots)=-(a_1, a_2, \dots).$ This yields the relation
$a_{n+1}=-a_{n}$ for $n=1, 2, \dots$.

Hence the sequence $(a_i)_{i=1}^{\infty}$ is a geometric progression with initial value $a_1$ and ratio $-1$.
Therefore, the sequence $(a_i)_{i=1}^{\infty}$ such that
$a_i=(-1)^{i-1}a_1$ are eigenvectors corresponding to the eigenvalue $-1$.

Similarly, eigenvectors corresponding to the eigenvalue $3$ are geometric progression with initial value $a_1$ and ratio $3$, thus
$a_i=3^{i-1}a_1.$

### (b) Find a sequence $(a_i)_{i=1}^{\infty}$ satisfying $a_1=2, a_2=7$.

From part (a), we see that sequences
$\mathbf{v}_1=\big( (-1)^{i-1} \big)_{i=1}^{\infty} \text{ and } \mathbf{v}_2=\big( 3^{i-1})_{i=1}^{\infty}$ form a basis of $U$ consisting of eigenvectors of $T$. (We chose $a_1=1$.)
Hence any sequence $(a_i)_{i=1}^{\infty}$ can be written as a linear combination of these two vectors:
\begin{align*}
(a_i)_{i=1}^{\infty} &=c_1\mathbf{v}_1+c_2\mathbf{v}_2\\
&=c_1\big( (-1)^{i-1} \big)_{i=1}^{\infty}+c_2\big( 3^{i-1})_{i=1}^{\infty}
\end{align*}
for some $c_1, c_2$.

If the sequence satisfies the initial condition $a_1=2, a_2=7$, then we have
\begin{align*}
2&=a_1=c_1+c_2\\
7&=a_2=-c_1+3c_2.
\end{align*}

Solving this, we obtain $c_1=-1/4$ and $c_2=9/4$.
Hence we have
\begin{align*}
(a_i)_{i=1}^{\infty}&=-\frac{1}{4}\big( (-1)^{i-1} \big)_{i=1}^{\infty}+\frac{9}{4}\big( 3^{i-1})_{i=1}^{\infty}\6pt] &=\frac{1}{4}\big( (-1)^{i} \big)_{i=1}^{\infty}+\frac{1}{4}\big( 3^{i+1})_{i=1}^{\infty}\\[6pt] &=\frac{1}{4}\big( (-1)^{i}+ 3^{i+1} \big)_{i=1}^{\infty}. \end{align*} In summary, the sequence (a_i)_{i=1}^{\infty} satisfying the linear recurrence relation a_{n+2}=2a_{n+1}+3a_{n} with initial conditions a_1=2, a_2=7 is \[(a_i)_{i=1}^{\infty}=\frac{1}{4}\big( (-1)^{i}+ 3^{i+1} \big)_{i=1}^{\infty}.

## Related Question.

Check out the following problems about how to solve a linear recurrence relation using the vector space techniques, like the current problem.

### 1 Response

1. 03/03/2017

[…] general term $a_n$ of the sequence $(a_n)_{i=n}^{infty}$ is obtained in the previous post Solve a linear recurrence relation using vector space technique: [a_n=frac{1}{4} big( (-1)^n+3^{n+1} big).] (You may alternatively find this using an […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.

##### Quiz 7. Find a Basis of the Range, Rank, and Nullity of a Matrix

(a) Let \$A=\begin{bmatrix} 1 & 3 & 0 & 0 \\ 1 &3 & 1 & 2 \\ 1 &...

Close