Question

Solve the recurrence relation${\mathit{a}}_{\mathbf{n}}{\mathbf{=}\mathbf{a}}_{\mathbf{n}\mathbf{-}\mathbf{1}}^{\mathbf{3}}{\mathit{a}}_{\mathbf{n}\mathbf{-}\mathbf{2}}^{\mathbf{2}}$ if ${\mathit{a}}_{\mathbf{0}}\mathbf{=}\mathbf{2}$and${\mathit{a}}_{\mathbf{1}}\mathbf{=}\mathbf{2}$ . (See the hint for Exercise 9.)

Short answer

The solution of recurrence is

$\begin{array}{l}{a}_n=2^{b_n}\\ =2^{A{c_{-}}^n+B{c^n}_{-}}\end{array}$

Step-by-step solution

Given data

We have given,

$\begin{array}{l}{a}_0=2\\ a_1=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.

Transform the recurrence equation

Taking logarithms as the question suggests, we get:

$\log \left(a_n\right)=3\log \left(a_{n-1}\right)+2\log \left(a_{n-2}\right)$

Now use the substitution $b_n=\log \left(a_n\right)$to transform our equation into:

$b_n=3b_{n-1}+2b_{n-2}$

This can then be solved using the usual method described previously to give general solution:

$b_n=A{\left(c_{+}\right)}^n+B{\left(c_{-}\right)}^n$

where $c_{+},c_{-}=\frac{3\pm \sqrt{17}}{2}$

Inputting the initial conditions $b_0=0$and $b_1=1$then gives:

$\begin{array}{l}A=\frac{1-c_{-}}{c_{+}-c_{-}},\\ B=\frac{1-c_{+}}{c_{-}-c_{+}}\end{array}$

Hence, the solution of recurrence is

$\begin{array}{l}{a}_n=2^{b_n}\\ =2^{A{c_{-}}^n+B{c^n}_{-}}\end{array}$