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))#