Solve a Linear Recurrence Relation Using Vector Space Technique

Linear algebra problems and solutions

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

LoadingAdd to solve later


(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
\mathbf{u}_1 &=(1, 0, 3, 6, 21, \cdots )\\
\mathbf{u}_2 &=(0, 1, 2, 7, 20, \dots).

We find the matrix $A$ of $T$ with respect to the basis $B$.
We have
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.

Thus, the matrix $A$ for $T$ is
0 & 1\\
3 & 2

Then the eigenvalues of $T$ are eigenvalues of $A$.
The characteristic polynomial for $A$ is
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

(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:
(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}
for some $c_1, c_2$.

If the sequence satisfies the initial condition $a_1=2, a_2=7$, then we have

Solving this, we obtain $c_1=-1/4$ and $c_2=9/4$.
Hence we have
(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}.
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)

LoadingAdd to solve later

More from my site

You may also like...

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 […]

Leave a Reply

Your email address will not be published. Required fields are marked *

More in Linear Algebra
Introduction to Linear Algebra at the Ohio State University quiz problems and solutions
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 &...