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

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

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