Question

Solve the recurrence relation ${\mathit{a}}_{\mathbf{n}}{\mathbf{=}\mathbf{a}}_{\mathbf{n}\mathbf{-}\mathbf{1}}^{\mathbf{2}}\mathbf{/}{\mathit{a}}_{\mathbf{n}\mathbf{-}\mathbf{2}}$if ${\mathit{a}}_{\mathbf{0}}\mathbf{=}\mathbf{1}$and ${\mathit{a}}_{\mathbf{1}}\mathbf{=}\mathbf{2}$. [Hint: Take logarithms of both sides to obtain a recurrence relation for the sequence$\mathit{l}\mathit{o}\mathit{g}{\mathit{a}}_{\mathbf{n}}\mathbf{,}\mathbf{n}\mathbf{=}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{\dots }\mathbf{]}$

Short answer

The solution is

$\begin{array}{c}\log a_n=\log n\\ a_n=2^n\\ \end{array}$

Step-by-step solution

Given data

We have given,

$\begin{array}{c}{a}_n=\frac{a_{n-1}^2}{a_{n-2}}\\ a_0=1\\ a_1=2\\ \end{array}$

Definition

The equation is said to be linear homogeneous difference equation if and only if $\mathit{R}\left(n\right)\mathbf{=}\mathbf{0}$and it will be of order n.

The equation is said to be linear non-homogeneous difference equation if$\mathit{R}\left(n\right)\mathbf{\ne }\mathbf{0}$.

SOLUTION HOMOGENEOUS RECURRENCE RELATION

Given:

$\begin{array}{c}{a}_n=\frac{a_{n-1}^2}{a_{n-2}}\\ a_0=1\\ a_1=2\\ \end{array}$

Take the logarithm of each side of the recurrence relation:

$\begin{array}{cc}\log a_n& =\log \frac{a_{n-1}^2}{a_{n-2}}\\ & =\log a_{n-1}^2-\log a_{n-2}\\ & =2\log a_{n-1}-\log a_{n-2}\\ \log a_0& =\log 1=0\\ \log a_1& =\log 2=1\\ & \end{array}$

If we let $b_n=\log a_n$, then we obtain the following linear recurrence relation:

$\begin{array}{c}{b}_n=2b_{n-1}-b_{n-2}\\ b_0=0\\ b_1=1\\ \end{array}$

Let $b_n=r^2,b_{n-1}=r$and $b_{n-2}=1$

$\begin{array}{cccc}{r}^2& =2r-1& & \\ r^2-2r+1& =0& & \text{Characteristic}\text{equation}\\ {(r-1)}^2& =0& & \\ r-1& =0& & \text{Zero}\text{product}\text{property}\\ r& =1& & \\ & & & \end{array}$

SOLUTION NON-HOMOGENEOUS RECURRENCE RELATION

The solution of the recurrence relation is of the form$a_n={\alpha }_1{r}_1^n+{\alpha }_{2}n{r}_1^n+\dots +{\alpha }_k{n}^{k-1}{r}_1^n$

with $r_1$a root with multiplicity $k$f the characteristic equation.

$\begin{array}{cc}{b}_n& ={\alpha }_1·1^n+{\alpha }_2·n·1^n\\ & ={\alpha }_1+{\alpha }_{2}n\\ & \end{array}$

Use initial conditions:

$\begin{array}{cc}& 0=b_0={\alpha }_1\\ & 1=b_1={\alpha }_1+{\alpha }_2\\ & \end{array}$

Determine ${\alpha }_2$

$\begin{array}{l}{\alpha }_2=1-{\alpha }_1\\ =1-0\\ =1\end{array}$

Thus, the sequence $\left\{b_n\right\}$then becomes:

$\begin{array}{l}{b}_n={\alpha }_1+{\alpha }_{2}n\\ =0+1·n\\ =n\end{array}$

Using $b_n=\log a_n$

Hence, the solution is

$\begin{array}{c}\log a_n=\log n\\ a_n=2^n\\ \end{array}$