How do you write a recursive formula for a sequence whose first three terms are 1, 1, and 3?
1 Answer
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
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,...
Bonus
Given such a recursive definition, how can we derive a general formula for
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))