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

1 Answer
Oct 22, 2016

One possibility would be:

{ (a_1 = 1), (a_2 = 1), (a_n = a_(n-2) + 2a_(n-1) " for " n >= 3) :}

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:

{ (a_1 = 1), (a_2 = 1), (a_n = a_(n-2) + 2a_(n-1) " for " n >= 3) :}

Such a rule would result in a sequence that starts:

1, 1, 3, 7, 17, 41, 99,...

color(white)()
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+2x

Hence:

0 = x^2-2x-1 = (x-1)^2-(sqrt(2))^2 = (x-1-sqrt(2))(x-1+sqrt(2))

So:

x = 1+-sqrt(2)

So look for a formula of the form:

a_n = A(1+sqrt(2))^n + B(1-sqrt(2))^n

Then:

1 = a_1 = A(1+sqrt(2))+B(1-sqrt(2))

1 = a_2 = A(1+sqrt(2))^2+B(1-sqrt(2))^2

color(white)(1 = a_2) = A(3+2sqrt(2))+B(3-2sqrt(2))

Hence:

A = (sqrt(2)-1)/2

B = -(sqrt(2)+1)/2

So:

a_n = 1/2((sqrt(2)-1)(1+sqrt(2))^n-(sqrt(2)+1)(1-sqrt(2))^n)

color(white)(a_n) = 1/2((1+sqrt(2))^(n-1)+(1-sqrt(2))^(n-1))