The Fibonacci sequence is defined by *a*1 = *a*2 = 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 *n*th 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 *a*1 = 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, *a*1 = *a*2 = 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 *a*2 = 3. The Pell sequence has *a*1 = 1, *a*2 = 2, *a*(*n* + 2) = 2*a*(*n* + 1) + *a*(*n*). It’s possible to generalize even more, for example to *a*1 = *a*2 = *a*3 = 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) + … + *k*1*a*(*n*) a Fibonacci-type sequence, where the Fibonacci sequence has *t* = 2, *k*1 = *k*2 = 1, *a*1 = *a*2 = 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) + … + *k*1*a*(*n*) with *k*1 != 0, then we must have *r*^(*n* + *t*) – *k*(*t*)*r*^(*n* + *t* – 1) – … – *k*1*r*^*n* = 0 for all *n*. Dividing throughout by *r*^*n*, we get *r*^*t* – *k*(*t*)*r*^(*t* – 1) – … – *k*1 = 0. The constants *t*, *k*1, *k*2, …, *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 *c*1*r*1^*n* + *c*2*r*2^*n* + … + *c*(*t*)*r*(*t*)^*n*. The initial conditions on *a*1, *a*2, …, *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*^*t* – *k*(*t*)*r*^(*t* – 1) – … – *k*1, 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 *k*1 = 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) – … – *k*1*nr*^*n* = 0. Divide by *r* to get (*n* + *t*)*r*^(*n* + *t* – 1) – *k*(*t*)(*n* + *t* – 1)*r*^(*n* + *t* – 2) – … – *k*1*nr*^(*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*‘ + *f*‘*g*, so (*f**(*x* – *r*)^2)’ = *f*‘*(*x* – *r*)^2 + 2*f**(*x* – *r*), which is divisible by *x* – *r*. The above polynomial is the derivative of *r*^(*n* + *t*) – *k*(*t*)*r*^(*n* + *t* – 1) – … – *k*1*r*^*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) = 2*a*(*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 – 2*r* + 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 *a*1 and common difference *d* = *a*2 – *a*1 can be written as (*a*1 – *d*)*1 + *d***n*.

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

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!

It’s worth mentioning that the value of

(sqrt(5)+1)/2is 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.

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

While we’re at it, one characterization of the Fibonacci sequence for

n> 1 is thata(n+ 1) is the integer nearest to phi*a(n). You can verify this by noting that for largen, the sequence is dominated by phi^n/SQRT(5), and the error term (1 – phi)^n/SQRT(5) tends to 0.Alon, I often see phi used to represent Phi-1. That is, phi (lower-case) is also 1/Phi (upper-case).

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.

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

I have no idea what MathML scripts are.

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?

MathML

No scripts in WordPress.com, I think.

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

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

φ+1=Φ

Φ+1=Φ^2

We really do need a way to superscript.

Ah, figured out how to do it.

²=²

Thus, Φ+1=Φ²

[…] 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 + […]

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

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