## Fibonacci-Type Sequences

The Fibonacci sequence is defined by a1 = a2 = 1, a(n + 2) = a(n + 1) + a(n). Its first few terms are then 1, 1, 2, 3, 5, 8, 13, 21, 34… That definition is called recursive, because the nth term depends on previous term, rather than just on n. Sequences can have recursive and non-recursive definitions at the same time: for instance, a(n) = n defines the same sequence as a1 = 1, a(n + 1) = a(n) + 1.

Given that, it might be interesting to look for a non-recursive definition of the Fibonacci sequence. Unfortunately, the most obvious way to start, expanding a(n + 1) and a(n) recursively to get the expansion of a(n + 2), ends up yielding the same recursive definition.

Fortunately, there’s already a known closed form definition: a(n) = (((1 + SQRT(5))/2)^n – ((1 – SQRT(5))/2)^n)/SQRT(5). The easiest proof that this defines the Fibonacci sequence is that the three conditions of Fibonacci are satisfied.

By direct calculation, a1 = a2 = 1. The recursion relation is satisfied since ((1 + SQRT(5))/2)^(n + 2) = (((1 + SQRT(5))/2)^2)(((1 + SQRT(5))/2)^n) = ((3 + SQRT(5))/2)(((1 + SQRT(5))/2)^n) = ((1 + SQRT(5))/2)(((1 + SQRT(5))/2)^n) + ((1 + SQRT(5))/2)^n = ((1 + SQRT(5))/2)^(n + 1) + ((1 + SQRT(5))/2)^n, and similarly for (1 – SQRT(5))/2.

Now, there are other sequences satisfying similar conditions. The Lucas sequence has the same recursion relation as the Fibonacci sequence, but has a2 = 3. The Pell sequence has a1 = 1, a2 = 2, a(n + 2) = 2a(n + 1) + a(n). It’s possible to generalize even more, for example to a1 = a2 = a3 = 1, a(n + 3) = a(n + 2) + a(n + 1) + a(n); that sequence begins with 1, 1, 1, 3, 5, 9, 17, 31, 57, 105…

Let’s call every sequence defined by a(n + t) = k(t)a(n + t – 1) + … + k1a(n) a Fibonacci-type sequence, where the Fibonacci sequence has t = 2, k1 = k2 = 1, a1 = a2 = 1.

Every Fibonacci-type sequence has a closed form non-recursive equation. The idea is to use the recursion condition to derive a space of closed form equations satisfying the condition, and then use the initial conditions to pick a single sequence in the space.

For example, with the Fibonacci rule, the space consists of all sequences of the form c((1 + SQRT(5))/2)^n + d((1 – SQRT(5))/2)^n. The Fibonacci sequence then has c = 1/SQRT(5), d = -1/SQRT(5). The Lucas sequence has c = 1/2 + 1/SQRT(20), d = 1/2 – 1/SQRT(20).

The idea is this: if r^n is a sequence satisfying the recursion condition a(n + t) = k(t)a(n + t – 1) + … + k1a(n) with k1 != 0, then we must have r^(n + t) – k(t)r^(n + t – 1) – … – k1r^n = 0 for all n. Dividing throughout by r^n, we get r^tk(t)r^(t – 1) – … – k1 = 0. The constants t, k1, k2, …, k(t) are all specified by the condition, so it’s a polynomial in r, which we can solve. That polynomial will in general have t different roots, giving t different possible values of r.

In that case, the general form of a sequence satisfying the recursion condition will be c1r1^n + c2r2^n + … + c(t)r(t)^n. The initial conditions on a1, a2, …, a(t) then give t linear equations in t variables, whence comes the precise definition of the sequence.

There are two reasons this might not work. First, the linear equations need not have a single solution. And second, sometimes the polynomial r^tk(t)r^(t – 1) – … – k1, which I will call the associated polynomial, has fewer than t roots..

The first problem isn’t really a problem. It can be shown that a system of t linear equations in t variables has a single solution if and only if the associated coefficient matrix, in this case defined by a(i, j) = r(j)^i, has nonzero determinant. Now divide each column by r(j). The matrix has zero determinant iff there’s a linear relation on 1, r(j), …, r(j)^(t – 1) for all j. But that will give another polynomial of degree less than t that all the roots of the associated polynomial satisfy, which is a contradiction since there are t roots. Note that if r(j) is ever zero, then k1 = 0, which contradicts the definition of a Fibonacci-type sequence.

The second is trickier. If we’re working over the complex numbers, then every polynomial of degree t has t roots, but some of them might be repeated. For that, note that (n^k)r^n is a suitable sequence when r is repeated at least k + 1 times in the associated polynomial.

To see why, first consider k = 1, and note that we must have (n + t)r^(n + t) – k(t)(n + t – 1)r^(n + t – 1) – … – k1nr^n = 0. Divide by r to get (n + t)r^(n + t – 1) – k(t)(n + t – 1)r^(n + t – 2) – … – k1nr^(n – 1) = 0.

If r is a repeated root of the associated polynomial, then it’s a root of both the polynomial and its derivative, defined by (x^m)’ = mx^(m – 1); this is because the derivative satisfies (fg)’ = fg‘ + fg, so (f*(xr)^2)’ = f‘*(xr)^2 + 2f*(xr), which is divisible by xr. The above polynomial is the derivative of r^(n + t) – k(t)r^(n + t – 1) – … – k1r^n, so given that r is a repeated root, nr^n does indeed satisfy the recursion condition.

This generalizes easily to k > 1. First, r has multiplicity at least k + 1 iff it divides the associated polynomial and its first k derivatives. For the actual derivation of the polynomial from (n^k)r^n, divide by r, take a formal antiderivative, then divide by r again, and so on, until you get the associated polynomial.

Even in that case, the determinant of the associated matrix is not zero, because the relation that generates a polynomial of degree at most t – 1 will then show that this polynomial has each r(j) as a root with the same multiplicity as in the associated polynomial.

Finally, if this seems too detached from ordinary sequences for you, note that arithmetic and geometric sequences are both Fibonacci-type. Every arithmetic sequence satisfies a(n + 2) = 2a(n + 1) – a(n), with the initial conditions determining the first term and the common difference. Every geometric sequence with common quotient q satisfies a(n + 1) = qa(n).

In the arithmetic case, the associated polynomial is r^2 – 2r + 1, which has 1 as a double root. So the space is generated by 1^n and n*1^n, or, if you will, by the constant sequence 1 and the sequence n. And indeed, every arithmetic sequence with first term a1 and common difference d = a2 – a1 can be written as (a1 – d)*1 + d*n.

In the geometric case, it’s even easier: the associated polynomial is rq, whose sole root is q. The space is generated by q^n, and indeed a geometric sequence with first term a1 and common quotient q can be written as (a1/q)*q^n.

### 18 Responses to Fibonacci-Type Sequences

1. Tyler DiPietro says:

Due to the generality of function concept, it’s not surprising that a recurrent function like one that produces the the Fibonacci sequence has a closed analog. But I’ve never really thought about it this in depth. Great post!

2. whig says:

It’s worth mentioning that the value of (sqrt(5)+1)/2 is also known as Phi or the golden ratio.

Phi is also the solution to the equation, x2-x-1=0.

It has a lot of interesting properties.

3. whig says:

My sup notation did not work in the comment. The equation is x^2-x-1=0.

4. Alon Levy says:

While we’re at it, one characterization of the Fibonacci sequence for n > 1 is that a(n + 1) is the integer nearest to phi*a(n). You can verify this by noting that for large n, the sequence is dominated by phi^n/SQRT(5), and the error term (1 – phi)^n/SQRT(5) tends to 0.

5. whig says:

Alon, I often see phi used to represent Phi-1. That is, phi (lower-case) is also 1/Phi (upper-case).

6. Alon Levy says:

Ah… when I wrote phi in the above comment, I meant (1 + SQRT(5))/2.

One of these days, I’m going to write a page (i.e. something permanent like the About Me page) about my mathematical notation.

7. Tyler DiPietro says:

Can you use MathML scripts in WordPress? That might be worth looking up.

8. Alon Levy says:

I have no idea what MathML scripts are.

9. SLC says:

Re Levy

I understand that there is a concept known as a Fibonacci search which is used to solve certain types of non-linear programming problems. Is this search technique related to the Fibonacci sequence?

10. Tyler DiPietro says:

MathML

11. whig says:

No scripts in WordPress.com, I think.

12. whig says:

But we can use &Phi;=Φ and &phi=φ.

13. whig says:

I think it’s more readable to use Φ instead of saying (1+sqrt(5))/2 all the time.

14. whig says:

φ+1=Φ
Φ+1=Φ^2

We really do need a way to superscript.

15. whig says:

Ah, figured out how to do it.

&sup2;=²

Thus, Φ+1=Φ²

16. […] Sequences, Part 2 Recall from part 1 that a sequence is said to be of Fibonacci type if it’s given by the recursion relation a(n + […]

17. fall styles says:

fall styles…

[…]Fibonacci-Type Sequences « Abstract Nonsense[…]…

18. Matthew says:

I don’t understand I either can’t see it or still need more information about Fibonacci-type sequence. Here is my problem

Consider the following sequence: 12, 4, 16, …, 36.
What is the missing number?
a. 18
b. 22
c. 20
d. 30