This famous sequence is a recurrence relation, in which each entry is the result of adding the previous two entries. There are variants on it that start with different values, but the original starts with a pair of 1 entries; adding those gives 2, adding that to the last 1 gets 3; adding that to the 2 gets 5, and so on, producing
We can equally wind the rule backwards – subtract an entry from the one after it to get the one before it – to find out what comes before where we start. If we'd started with two successive entries from the list above, to get the part of the sequence from them onwards, we'd thus be able to wind backwards to discover the earlier 1, 1 that we could hae started at to get to our alternative start. We can, naturally, wind backwards from that 1, 1, too: clearly the entry before must have been 0, and the one before that 1; before that we need −1 to add to that 1 to get 0. Before that −1 we need a 2 to add to it to get 1; before that −3 and, continuing, 5, −8, 13; so you might have noticed that, aside from sign, these are the same entries as above.
Since that means the sequence stretches indefinitely in both directions,
we'll need the integers to index the sequence; and changing which entry gets to
be at index 0 doesn't really change the sequence, only how we index it.
However, we've just seen how winding backwards produced the same values, aside
from sign in alternating entries, as winding forward; so chosing to index from
the zero in the middle
of that pattern seems like a good plan. That
gives indices 1 and 2 to the two 1s with which it's traditional to start. So
let's define a function ({integers}: fib :{integers}), to represent this
sequence, by:
The former is known as the initial condition
and the latter as
the recurrence rule
or recurrence relation. The recurrence rule can
equally be re-written as fib(n−1) = fib(n+1) −fib(n) for every
integer n, which is how we work backwards to get at fib's entries at negative
index. Given the recurrence rule, we could actually replace the initial
condition with a statement of fib's value at any two distinct indices, notably
the traditional fib(1) = 1 = fib(2).
(I can equally phrase the initial conditions as (:fib:2) = 2 – because, in my notation, 2 = {0, 1} is the identity on its two members and fib, restricted to its members, also maps each to itself – but this is perhaps not the most illuminating way to express it.)
Given why I picked this indexing, let's take a look at how the negative entries relate to the corresponding positive ones. Plainly −fib(0) = fib(−0) since 0 = −0; and 0 is even. Next, using the reverse recurrence rule, fib(−1) = fib(1) −fib(0) = fib(1), thanks to fib(0) = 0; and 1 is odd. Finally, consider any positive natural n for which, for all i in n, fib(−2.i) = −fib(2.i) and fib(−(2.i +1)) = fib(2.i +1); we've just seen that this is true for n = 1 = {0}, for which the only i in n is 0. As n is positive, i = n−1 is in n, so our precondition tells us
The recurrence rule, in its backwards form, tells us
So the condition I presumed was true for every i in n implies itself also for n, hence for every i in n+1 and, inductively, for every natural larger than n. Given that the precondition is true for n = 1, we can thus induce that it is true for every positive natural n.
We can summarise this result as fib(−odd) = fib(odd) and fib(−even) = −fib(even). Since fib's entries at negative index are thus entirely determined by its entries at positive index, negative indices mostly drop out of the discussion hereafter.
Consider any three consecutive entries in a sequence satisfying the recurrence rule. From any two of these, we can infer the third as a sum or difference. Consequently, any common factor shared by two of them is in fact shared by all three. An entry on either side of them plus the two of them closest to it then have two sharing that factor so the new addition also shares it and, inductively, we can infer that any common factor, of two entries either adjacent to one another or on either side of a shared neighbour, is in fact a factor of all entries in the sequence. So take the highest common factor of any two adjacent entries in a sequence satisfying the rule, divide every entry in the sequence by that and you'll obtain a sequence in which entries adjacent to one another or on either side of a third are coprime.
Conversely, if any two entries in a sequence satisfying the recurrence rule are coprime, every entry in the sequence is coprime to the two entries before it and the two entries after it. In particular, fib has 1 as an entry (at three indices, no less; but one would sufffice), which is coprime to every number, hence fib is of this later type. I'll describe such sequences as coprime, even though some entries will have common factors; they'll just be separated by more than two other entries.
Consider a coprime sequence satisfying Fibonacci's recurrence rule. If two adjacent entries are odd, their sum and difference are even, so the entries before and after them are both even. Every even entry is coprime to the two entries before it and the two after it, so there are pairs of adjacent odd entries before and after each even entry. So every sequence satisfying the rule, that has any coprime entries, has every third entry even, the others all being odd. With the boundary condition I've chosen, fib(3.n) is even for every integer n.
What about other factors ? That actually turns out to be more complex, so I'm exploring it on another page. Every sequence satisfying the recurrence rule does contain multiples of at least 3 (every fourth entry) and 7 (every eighth entry); but some sequences follow the rule without containing any multiples of (at least) 5, 11 or 13. Any sequence, satisfying the recurrence rule, that has a zero entry will necessarily include multiples of all primes (since that zero entry is one, and the sequence necessarily cycles, modulo any given finite value). In particular, fib contains multiples of every prime.
Leave aside the initial condition for a moment and let's consider what possible functions could obey the recurrence rule. One possibility might be a sequence where each entry is simply some constant times the previous, (: k.power(n, h) ←n :) for some constants k and h. To satisfy the recurrence rule, this would need
for every integer n. Of course, this is trivially satisfied if k = 0,
but that's not very interesting. For any other value of k, we can cancel it
from all three terms; we can also cancel factors of h, reducing the condition to
h.h = h +1. That's equivalent to 0 = h.h −h −1 = power(2, h
−1/2) −1/4 −1. Multiplying through be 4, this becomes 5 =
power(2, 2.h −1) implying 2.h −1 = ±√5, hence h = (1
±√5)/2. The product of the two values is (1 −5)/4 =
−1, so one of them is negative; the positive one, known
as the golden ratio
, is g = (1 +√5)/2.
(I'll return to this, below.) Our two candidate values
for h are thus g and −1/g; given that g.g = g +1, whence g = 1 +1/g, that
−1/g is also 1 −g.
Our recurrence rule is linear, in the sense that if two sequences e and f both abide by it, e(i+1) = e(i) +e(i−1) and f(i+1) = f(i) +f(i−1), then so does the result of arbitrarily scaling either and adding the results. Given that we have two solutions for h, we thus have two such sequences at our disposal, (: power(n, g) ←n :) and (: power(n, −1/g) ←n :), so we can say that, for any constants u and v,
satisfies the recurrence rule; that is, F(u, v, n+1) = F(u, v, n) +F(u, v, n−1) for every integer n. Notice that power(n, −1/g) can equally be written power(−n, −g). Now consider any function f that does satisfy the recurrence rule, and suppose we're told its values at two distinct integers, n and m. That imposes two constraints and we have two constants u and v to chose, so can we find a u and v that will match them ? If F(u, v, n) = f(n) and F(u, v, m) = f(m) then:
Divide each by its power of −g to get:
Subtract
The scaling of u is by a difference of distinct powers of −g.g = −(1 +g), with 1 +g > 1, so non-zero, so its distinct powers are distinct, making the scaling non-zero, so we can divide by it and rarrange this as:
In essentially the same way, just dividing by the power of g instead, we get
Given how we obtained these, they necessarily ensure F(u, v, n) = f(n) and F(u, v, m) = f(m); and F(u, v, i) is then fully determined for all integrs i. If I can show that agreeing in two places ensures two functions obeying our recurrence rule agree everywhere, this'll imply that the various F(u, v) are all the possible solutions to this rule.
Before I move on to attempt that, let's just pause to see what it gives for the standard initial condition above. 0 = F(u, v, 0) implies v = −u; and 1 = F(u, −u, 1) = u.(g −1/g) = u and we can write:
Given that g, √5 and −g are irrational, it is mildly astonishing that every integer n gets an integer value for that expression. That also leads to some imprecision in computing by this formula in practice, for larger n.
Now let's get back to that question of whether we've found all solutions: can two functions satisfying our recurrence rule agree in to values but disagree somewhere else ? As previously noted, our recurrence rule is linear, so the difference between our two functions will also satisfy the rule; and it's zero at two distinct indices. So we can rephrase our question as: can a function satisfy Fibonacci's recurrence rule, have two distinct indices at which it's zero and some indices at which it's not ?
First let's take the case of a function f that obeys the rule and is zero at one integer input; let that integer input be j. Helpfully, we already know about one such function, since fib(0) = 0; so f(j) = 0 = fib(0). Consider g = (: f(j+n) −f(j+1).fib(n) ←n :{integers}). By construction, g(0) and g(1) are both 0; and the recurrence rule is linear, so g also satisfies it; we have g(i) = 0 for all i in {0, 1} = 2, so suppose g(i) = 0 for all i in some natural n ≥ 2; then g(n−1) = 0 = g(n−2) and g(n) = 0 +0 = 0, ensuring that g(i) = 0 for all i in n+1; given that this was true for n = 2 we can induce that it is true for every natural n and hence that g(i) = 0 for every natural i. By identical reasoning we can show g(−i) = 0 for every natural i and thus that g = ({0}: |{naturals}), hence f(j+n) = f(j+1).fib(n) for every natural n. In other words, any sequence satisfying Fibonacci's recurrence rule, that has a zero entry, is just fib scaled by some constant and with an offset applied to its indexing.
Observe that, for a sequence f obeying the rule, f(i) > 0 implies f(i+1) > f(i−1) and f(i+2) > f(i+1). Further, f(i) ≥ f(i−1) > 0 implies f(i+1) > f(i) > 0 and, inductively, that f(n+1) > f(n) > 0 for every integer n ≥ i. As fib(2) ≥ fib(1) > 0 we can duly infer that fib(i) > 0 for every positive integer i and, in particular, no positive i has fib(i) = 0. Given that every i has fib(−i) = ±fib(i) and negating a non-zero value gives a non-zero value, this implies that every integer i ≠ 0 has a non-zero fib(i) and 0 is the only index at which fib is 0.
So if f(j+n) = f(j+1).fib(n) and there is some index other than j at which f is zero, i.e. some non-zero integer n for which 0 = f(j+n) = f(j+1).fib(n), then fib(n) is non-zero (because n is), we can divide by it, so 0 = f(j+1) and f is everywhere zero. So the only sequence satisfying Fibonacci's recurrence rule that has value zero at two distinct indices is the everywhere-zero sequence; and, as a result, if two sequences satisfying the rule agree at two distinct inputs, they agree eveywhere, i.e. they are equal as sequences. This, in turn, implies that every sequence satisfying this recurrence rule is in fact F(u, v) for some constants u, v.
Let's have another interesting structural property: the sum of squares of two consecutive entries in fib is the entry whose (odd) index is the sum of the indices of the two consecutive entries. That is, fib(i).fib(i) +fib(i+1).fib(i+1) = fib(2.i +1). Proof: start by checking the cases i in 2 = {0, 1}, which are fib(2×0 +1) = fib(1) = 1 = 0×0 +1×1 = fib(0).fib(0) +fib(1).fib(1) and fib(2×1 +1) = fib(3) = 2 = 1×1 +1×1 = fib(1).fib(1) +fib(2).fib(2) – both follow the claimed relationship. Next observe, by expanding the positive square, that
and we're ready to prove the claimed property, by induction. Given a natural n ≥ 2 for which, for all i in n, our equation holds true, consider:
applying the recurrence rule twice. We can also apply a rearranged form of it, fib(k) = fib(k+1) −fib(k−1), to get rid of the remaining even-index term:
We can now apply our inductive hypothesis, with n−1 and n−2 as i in the two terms:
Apply the observation above with n = i+1 to one squared fib(n) and the two negative terms:
Combine the last with two of the squared fib(n−1)s,
Apply the recurrence rule to the last term:
Apply the observation above in reverse, now with n = i, to the result of that, eating one each of the squares in the process:
and we've shown that our result holds true also for n; hence, given it for i in {0, 1}, for every natural i.
Now let's consider negative indices. Helpfully, for any integer i, the squares of fib(i) and fib(−i) are equal. For negative integer index j, the negative index 2.j +1 is odd, hence fib(2.j +1) = fib(−(2.j +1)) = fib(2.(−j) −1) = fib(−j).fib(−j) +fib(−j−1).fib(−j−1) = fib(j).fib(j) +fib(j+1).fib(j+1), so the condition still applies. Thus, for any integer i, fib(2.i +1) = fib(i+1).fib(i+1) +fib(i).fib(i); every odd-index entry in Fibonacci's sequence is a sum of the squares of two adjacent entries in the sequence, whose indices sum to the odd-index of that entry.
Note that only the initial proof that the condition held for i in {0, 1} actually depended on the initial condition we've used to define fib, so any other initial condition that satisfies this same condition will also lead to the condition being true for every pair of consecutive positive indices; the case for negative indices will depend on whether the alternate initial condition roll backwards suitably.
The sum of powers formula for the Fibonacci sequence used powers of the golden ratio, (1 +√5)/2, the positive root of q.q = q +1; this shows up in diverse other places (e.g. some artists like the sides of their canvas in this proportion). That equation can be rearranged as q = 1 +1/q, which leads to the golden ratio having the continued fraction representation
If you truncate this (skip the 1/(…) at some depth) and expand it out, you start at the bottom with 1/1 and, at each step, invert the fraction and add one; if the fraction is a/b that gives you 1 +b/a = (a+b)/a which, inexorably, turns our 1/1 into 2/1, 3/2, 5/3, 5/8, 13/8 and generally f(i +1)/f(i) for successive i, yielding 1 +f(i)/f(i +1) = f(i +2)/f(i +1) at the next step. So truncating the continued fraction gives a fraction that's a ratio of successive terms of our sequence; however, there remains the question of whether that's actually any good as an approximation to the golden ratio.
The golden ratio is between 1 and 2; so successive powers of it get bigger. The other term in our sum for f(n) is a power of (1 −√5)/2; since 5 lies between 4 and 9, √5 lies between 2 and 3, so 1 −√5 lies between −2 and −1; half of this lies between −1 and −1/2, so successive powers of it (alternate in sign and) get smaller. Consequently, for large n, f(n) is dominated by power(n) of the golden ratio and the ratio of successive terms in the sequence, f(n+1)/f(n), approximates the golden ratio, doing so better for larger n. Thus, indeed, truncating our continued fraction representation of the golden ratio does give us a good approximation, better the deeper we go before truncating.
That ratio, furthermore, is always in coprime form: f(n+1) and f(n) have no common proper factor. This is easy to see if you simply run Euclid's algorithm to discover their highest common factor: the algorithm, at each step, reduces the larger value modulo the smaller and then repeats itself with the reduced value and the former smaller, which is now the larger value. For n>0, f(n)>0; thus, for n>1, f(1+n) = f(n) +f(n−1) > f(n); and, for n > 2, 2.f(n) = f(n+1) +f(n)− f(n−1) > f(n+1); so, for n > 2, f(n) < f(n+1) < 2.f(n) and f(n+1) reduced mod f(n) is just f(n+1) −f(n) = f(n−1). Thus each step of Euclid's algorithm just winds back down Fibonacci's sequence, replacing f(n+1) and f(n) with f(n) and f(n−1) until we get to f(2) = 1 and f(1) = 1, whose highest common factor is 1; from which, as Euclid's algorithm perserves the highest common factor of its pair of numbers, we can infer that f(n+1) and f(n) have 1 as highest common factor and thus are coprime.
This leads to successive entries in Fibonacci's sequence making good integers to use for a rectangle whose sides have to be whole numbers, if we want the aesthetically pleasing proportions of a golden rectangle. (This has ratio of sides equal to the golden ratio: cutting from it a square on its shorter side leaves a smaller rectangle in the same proportions; adding to it a square on its longer side yields another.) I use this, for example, in the default size of my grid for Conway's game of life. Since that also uses the Klein bottle's topology by default, with the shorter axis simply cycling and the longer one flipping the shorter each time round, a glider travelling round it will, by the time it's traversed the longer axis twice, be travelling parallel to how it started out and offset by 2.f(n+1) modulo f(n). Since 2.f(n+1) = 2.f(n) +2.f(n−1) = 2.f(n) +f(n−1) +f(n−2) +f(n−3) = 3.f(n) +f(n−3); so 2.f(n+1) modulo f(n) is just f(n−3).
So, modulo f(n), we now know f(n+1) = f(n−1) = −f(n−2) and
2.f(n+1) = f(n−3). Let's look next at 3.f(n+1) = f(n−1)
+f(n−3) = f(n−3) −f(n−2) = −f(n−4). Then
4.f(n+1) = 2.f(n−3) = f(n−2) +f(n−5), which I don't
immediately see an easy way to reduce to a single entry ! Speaking of the
sequence modulo various things, let's look at it modulo assorted early naturals
(with …
at the point – always where a 0 would follow a 1
– where it starts repeating itself):
Given that the golden ratio is (1 +√5)/2, each of its powers can be written a as sums of one diadic rational plus √5 times another. If we could work out a formula for what those diadic rationals are, we might in principle be able to use the power sequence formula, despite its irrational content, to compute the sequence using purely integer arithmetic. So let's see how that plays out when we try it.
So let (p, q) stand for (p +q.√5)/2, so that g = (1, 1); we get an arithmetic with simple additin of corresponding entries in pairs and a multiplication (a, b).(c, d) = ((a.c +5.b.d)/2, (a.d +b.c)/2). Let's look at the successive powers of g = (1, 1), starting with power(0, g): they are (2, 0), (1, 1), (3, 1), (4, 2), (7, 3), (11, 18), … and I notice a pattern, which sadly spell doom for the hoped-for project of using this to compute fib, because the second member of each pair is just fib; and the first members 2, 1, 3, 4, 7, 11, 18 also follow the Fibonacci recurrence rule. So these aren't going to give us a way to get at fib's entries by purely integer arithmetic, after all.
Still, now that I've stumbled on it, I'm interested to see what's going on here. If we write power(n, g) as (s(n), fib(n)) then we get (s(n+1), fib(n+1)) = power(n+1, g) = (s(n), fib(n)) = ((s(n) +5.fib(n))/2, (s(n) +fib(n))/2) whence 2.s(n+1) = s(n) +5.fib(n) and s(n) +fib(n) = 2.fib(n+1) = 2.fib(n) +2.fib(n−1). From the second of these we get s(n) = fib(n) +2.fib(n−1) = fib(n+1) +fib(n−1); and that necessarily satisfies the recurrence rule, since it's just a sum of two offset versions of fib and the rule is linear. So let's see whether that suffices to make the first condition true, too.
So, indeed, we have 2.power(n, g) = fib(n+1) +fib(n).√5 +fib(n−1) for each integer n; since power(n, g) and each of the offset or scaled versions of fib summed on the right all satisfy the recurrence relation, it suffices that this is true for two values of n, as it manifestly is for n = 0 and 1.
Written by Eddy.