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^t – k(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^t – k(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‘ + f‘g, so (f*(x – r)^2)’ = f‘*(x – r)^2 + 2f*(x – r), which is divisible by x – r. 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 r – q, 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.