# How do you write a recursive formula for a sequence whose first three terms are 1, 1, and 3?

Oct 22, 2016

One possibility would be:

$\left\{\begin{matrix}{a}_{1} = 1 \\ {a}_{2} = 1 \\ {a}_{n} = {a}_{n - 2} + 2 {a}_{n - 1} \text{ for } n \ge 3\end{matrix}\right.$

#### Explanation:

There is no recursive formula based simply on the value of the previous term, since it would have to give two different values (namely $1$ and $3$) based on the same previous value $1$.

So we may be dealing with something similar to a Fibonacci sequence, where each term depends on the two previous terms.

We can write a formula like this:

$\left\{\begin{matrix}{a}_{1} = 1 \\ {a}_{2} = 1 \\ {a}_{n} = {a}_{n - 2} + 2 {a}_{n - 1} \text{ for } n \ge 3\end{matrix}\right.$

Such a rule would result in a sequence that starts:

$1 , 1 , 3 , 7 , 17 , 41 , 99 , \ldots$

$\textcolor{w h i t e}{}$
Bonus

Given such a recursive definition, how can we derive a general formula for ${a}_{n}$ ?

One way is to note that the ratio between successive terms tends towards a limit.

Consider the sequence:

$1 , x , {x}^{2}$

If it satisfied our recursive step rule, then we would have:

${x}^{2} = 1 + 2 x$

Hence:

$0 = {x}^{2} - 2 x - 1 = {\left(x - 1\right)}^{2} - {\left(\sqrt{2}\right)}^{2} = \left(x - 1 - \sqrt{2}\right) \left(x - 1 + \sqrt{2}\right)$

So:

$x = 1 \pm \sqrt{2}$

So look for a formula of the form:

${a}_{n} = A {\left(1 + \sqrt{2}\right)}^{n} + B {\left(1 - \sqrt{2}\right)}^{n}$

Then:

$1 = {a}_{1} = A \left(1 + \sqrt{2}\right) + B \left(1 - \sqrt{2}\right)$

$1 = {a}_{2} = A {\left(1 + \sqrt{2}\right)}^{2} + B {\left(1 - \sqrt{2}\right)}^{2}$

$\textcolor{w h i t e}{1 = {a}_{2}} = A \left(3 + 2 \sqrt{2}\right) + B \left(3 - 2 \sqrt{2}\right)$

Hence:

$A = \frac{\sqrt{2} - 1}{2}$

$B = - \frac{\sqrt{2} + 1}{2}$

So:

${a}_{n} = \frac{1}{2} \left(\left(\sqrt{2} - 1\right) {\left(1 + \sqrt{2}\right)}^{n} - \left(\sqrt{2} + 1\right) {\left(1 - \sqrt{2}\right)}^{n}\right)$

$\textcolor{w h i t e}{{a}_{n}} = \frac{1}{2} \left({\left(1 + \sqrt{2}\right)}^{n - 1} + {\left(1 - \sqrt{2}\right)}^{n - 1}\right)$