This famous sequence is a solution to 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 it's commonly taught as starting 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 have 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 fib(1) = 1 = fib(2) that I was taught in school.
The actual original form of the sequence was as answer to a question about scansion in Sanskrit poetry. Given words with one sylable or two, how many patterns of sylables can the words form in a poem of a given number of sylables ? For one sylable only, there is only one pattern, a single-sylable word; for a two sylable total, one can have two single-sylable words or a two-sylable word. For n+2 sylables, you can either add a two-sylable word to an n-sylable pattern or a single-sylable word to an (n+1)-sylable pattern. So that starts with 1, 2 unlike how I was initially taught it, starting 1, 1, or how I specify it here, starting 0, 1. (I can equally phrase my 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.) Quite by chance, my indexing delivers fib(5) = 5, fib(12) = power(2, 12). The latter is, aside from the 0 and 1 entries in fib (at indices −1, 0, 1 and 2) the only perfect square I've found in the sequence.
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) or as fib(−n) = −power(n, −1).fib(n). 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 at least 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.
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. This implies power(2, 2.h −1) = 4.(h.h −h) +1 = 5,
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.√5 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 two 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.
Given two sequences, f and e, that satisfy Fibonacci's recurrence relation and two integers i, m, observe:
Each end of this multiplies an entry from each sequence and adds the product of their respective predecessors; and we shift one pair forwards in its sequence, the other backwards, preserving the sums of the indices in each product. Thanks to that invariant, we can thus induce that, with m+i = n,
In particular, with e = fib so e(1) = 1 and e(0) = 0, so that f(n).e(1) +f(n−1).e(0) = f(n), this says that every sequence f satisfying the recurrence rule is
Another consequence of our invariant on products of adjacent pairs is:
which, with e = fib = f and i = m +1, becomes:
implying that every odd-index entry in fib is the sum of the squares of the two adjacent entries whose indices add up to the given odd index.
Notice that this is true equally for negative indices: the odd index entry is equal to the odd index entry with the corresponding positive index and the two entries whose squares we're taking are just the two positive-index entries whose squares add up to that, with the sign of one flipped, which is ignored by squaring.
With i = m +3 we likewise obtain
Squaring this, using the two distinct expressions for it, we get:
whence fib(2.m +3), fib(m).fib(m+3) and 2.fib(m+1).fib(m+2) constitute a pythagorean triple.
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 at least roughly 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, 8/5, 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), we find that 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 5.f(n+1) = = 2.f(n +1) +3.f(n +1) = f(n −3) −f(n−4) = f(n −5), 8.f(n+1) = (5 +3).f(n +1) = f(n−5) −f(n−4) = −f(n−6) and we have an emerging pattern: at least up to i = 6, mod f(n), we have f(i).f(n +1) = −power(i, −1).f(n−i). The case i = 0 is 0.f(n+1) which is zero and, of course, mod f(n) this is equal to −power(0, −1).f(n−0) = −f(n). When the pattern holds true for all i in some natural m ≥ 2, it implies f(m).f(n +1) = (f(m−1) +f(m−2)).f(n +1), with both m −1 and m −2 in m, whence, mod f(n), f(m).f(n +1) = power(m−2, −1).(f(n−(m−2)) −f(n−(m−1))) = power(m, −1).(f(n−m+1) −f(n−m+2)) = −power(m, −1).f(n −m), so whenever the pattern holds true for all members of some natural, it also holds true for that natural. Hence, by induction, it in fact holds true for every natural:
Now let's return to the value of the golden ratio expressed as a continued fraction. The general process of continued fractions is to express any number as a whole number plus or minus a fractional part, then to express that fractional part, which is smaller than 1, as the inverse of something bigger than 1, to which we can apply the same process. The 1 +1/(1 +1/(1 +…)) form only ever uses positive fractional parts but if we allow ourselves either positive or negative fractional parts, we can ensure they always lie between ±1/2 (inclusive) and thus their inverses are always ≥2 or ≤−2, ensuring we don't get 1 (or −1) as the whole number part. So let's try constructing a continued fraction that always uses the closest integer, rather than rounding down, for the integer part.
Since √5 is between 2 and 3, the golden ratio is between 3/2 and 2, so closer to 2 than to 1, so we're going to want to work out what 1/(2 −g) is. If we write x = 1/(2 −g), we get g = 2 −1/x which we can substitute into g.g = 1 +g to get 3 −1/x = (2 −1/x).(2 −1/x) = 4 −4/x +1/x/x whence 3/x = 1 +1/x/x or x = 3 −1/x = 3−1/(3 −1/(3 −…)) and g = 2 −1/(3 −1/(3 −1/(3 −(3 −…)))). The truncations of this give us 2, 5/3, 13/8, 34/21, fitting a pattern thus far of fib(2.n+1)/fib(2.n); as x = g +1 this implies the next refinement will use fib(2.n+2)/fib(2.n) for x hence 2 −fib(2.n)/fib(2.n+2) = (fib(2.n+2) +fib(2.n+1))/fib(2.n+2) = fib(2.n+3/)fib(2.n+2) thereby continuing the pattern at each step.
Given that the golden ratio is (1 +√5)/2, each of its powers can be written as a sum 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.
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). In particular, (a, b).(1, 1) = (2.b +(a +b)/2, (a +b)/2), so the successive powers of g = (1, 1), starting with power(0, g), are (2, 0), (1, 1), (3, 1), (4, 2), (7, 3), (11, 5), (18, 8), … and I notice a pattern, which sadly spells doom for the hoped-for project of using this to compute fib, because the second members of the pairs just form the sequence 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)).(1, 1) = ((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. Just as a sanity-check, let's now substitute that into
in which we can use the rule above for negating the input to fib, with the power of −1, to simplify as
which is exactly the analytic solution we got above. Thus my stray though on escaping the irrationals turns out to be no help at all, because the coefficients we would be combining to do that are exactly the values of fib that I was hoping to get at by expanding powers of g in terms of one diadic rational plus another scaled by √5. But at least it all checks out as consistent – and now I have a tidy way to work out the powers of the golden ratio.
Written by Eddy.