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

 
Add to solve later

Sponsored Links

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. Sequences satisfying linear recurrence relation form a subspace
2. Matrix representation of a linear transformation of subspace of sequences satisfying recurrence relation
3. Solve linear recurrence relation using linear algebra (eigenvalues and eigenvectors)

Click here if solved 9
Add to solve later

Sponsored Links