Question

Find the solutions of the simultaneous system of recurrence relations,

$\begin{array}{c}{\mathbf{a}}_{\mathbf{n}}\mathbf{=}{\mathbf{a}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{+}{\mathbf{b}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\\ {\mathbf{b}}_{\mathbf{n}}\mathbf{=}{\mathbf{a}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{-}{\mathbf{b}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\\ {\mathbf{a}}_{\mathbf{0}}\mathbf{=}\mathbf{1}\\ {\mathbf{b}}_{\mathbf{0}}\mathbf{=}\mathbf{2}\\ \end{array}$

Short answer

The solutions of recurrence are

$\begin{array}{l}{a}_{2k}=2^k\\ a_{2k+1}=3·2^k\\ b_{2k}=2^{k+1}\\ b_{2k+1}=-2^k\end{array}$

Step-by-step solution

Given data

We have given,

$\begin{array}{c}{a}_n=a_{n-1}+b_{n-1}\\ b_n=a_{n-1}-b_{n-1}\\ a_0=1\\ b_0=2\\ \end{array}$

Definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms.

Adding the recurrence relations

Given:

$\begin{array}{c}{a}_n=a_{n-1}+b_{n-1}\\ b_n=a_{n-1}-b_{n-1}\\ a_0=1\\ b_0=2\\ \end{array}$

Add the two recurrence relations:

$a_n+b_n=2a_{n-1}+b_{n-1}-b_{n-1}$

Solve the equation to $b_n$:

$b_n=2a_{n-1}-a_n$

Let us then use $b_{n-1}=2a_{n-1}-a_{n-1}$in the first recurrence relation.

$\begin{array}{l}{a}_n=a_{n-1}+b_{n-1}\\ =a_{n-1}+2a_{n-2}-a_{n-1}\\ =2a_{n-2}\end{array}$

$a_n=2a_{n-2}$

$a{}_0=1$

$\begin{array}{l}{a}_1=a_0+b_0\\ =1+2\\ =3\end{array}$

Simplify the recurrence relation

Repeatedly apply the recurrence relation
$n$even

There exists an integer $k$such that $n=2k$

$\begin{array}{l}{a}_n=a_{2k}\\ =2a_{n-2}\\ =2^2{a}_{n-4}\dots \\ =2^k{a}_0\\ =2^k\end{array}$

$n$odd

There exists an integer $k$such that$n=2k+1$

$\begin{array}{l}{a}_n=a_{2k+1}\\ =2a_{k-1}\\ =2^2{a}_{k-3}\dots \\ =2^k{a}_1\\ =3·2^k\end{array}$

Thus, we have then solved the recurrence relation of $a_n$.

$b_n=2a_{n-1}-a_n$

Use the recurrence relation of $a_n\left(a_{2k}=2^k\right.$and $\left.a_{2k+1}=3·2^k\right)$

$\begin{array}{cc}{b}_{2k}& =2a_{2k-1}-a_{2k}\\ & =2a_{2(k-1)+1}-a_{2k}\\ & =2·3·2^{k-1}-2^k\\ & =3·2^k-2^k\\ & =2·2^k\\ & =2^{k+1}\\ b_{2k+1}& =2a_{2k}-a_{2k+1}\\ & =2·2^k-3·2^k\\ & =(2-3)·2^k\\ & =(-1)·2^k\\ & =-2^k\\ & \end{array}$

Hence, the solutions of recurrence are

$\begin{array}{l}{a}_{2k}=2^k\\ a_{2k+1}=3·2^k\\ b_{2k}=2^{k+1}\\ b_{2k+1}=-2^k\end{array}$