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$.
Sponsored Links
Contents
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.
- Sequences satisfying linear recurrence relation form a subspace
- Matrix representation of a linear transformation of subspace of sequences satisfying recurrence relation
- Solve linear recurrence relation using linear algebra (eigenvalues and eigenvectors)
Add to solve later
Sponsored Links
1 Response
[…] 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 […]