# Ratios of Subsequent Terms in Generalized Fibonacci Sequences

The Fibonacci sequence begins 0, 1, 1, 2, 3, 5, 8, etc.  Each subsequent term is the sum of the previous two.  As the terms get larger and larger, the ratio of two subsequent terms approaches a limit, the golden ratio or Φ, (1 + sqrt(5))/2, or about 1.6180339.  To see this, assume that each term is r times the previous term:  Fn+1 = r Fn, and Fn = r Fn-1.  Then, the Fibonacci recurrence equation

Fn+1 = Fn + Fn-1

becomes

r2 Fn-1 = r Fn-1 + Fn-1, or
r2 = r + 1.

The last equation is easily solved by the quadratic formula to give r = Φ.

This process can be extended to variations on the Fibonacci sequence by letting the new term be a weighted sum of the previous two terms:

Fn+1 = a Fn + b Fn-1

for some numbers a and b.  Then, by the same analysis, the ratio of subsequent terms will approach a limit r, r = (a + sqrt(a2 + 4b))/2.  Here are some values of the ratio r for various a's and b's:

 a b r 1 1 1.618 2 1 2.414 3 1 3.303 1 2 2 2 2 2.732 3 2 3.562 1 3 3 2 3 2.303 3 3 3.791

This table can be extended indefinitely.  Then, sort it by increasing values of r (when there is a tie, sort by increasing values of sqrt(a2 + b2)).  This generates two sequences, A, the sequence of the a values, and B, the sequence of the b values.  The A sequence begins:

1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 1, 3, 2, 4, 1, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 1, 4, 2, 1, 3, 5, 2, 4, 1, 3, 2, 5, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, …

and the B sequence begins:

1, 2, 3, 1, 4, 2, 5, 3, 6, 7, 4, 1, 8, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12, 13, 9, 5, 1, 14, 10, 6, 15, 2, 11, 16, 7, 12, 3, 17, 8, 13, 18, 4, 9, 14, 19, 5, 10, 15, 20, 21, 16, 11, 6, 1, 22, 17, 12, 7, 23, 18, 2, 13, 24, 8, 19, 25, 14, 3, 20, 9, 26, 15, 21, 4, 27, 10, 16, 22, 28, 5, 11, 17, 23, 29, 6, 12, 18, 24, 30, 31, 25, 19, 13, 7, 1, 32, 26, 20, 14, …

These sequences count each other--the terms in B count up how many times each number in A has shown up.  The first three terms of A are 1 and the first three terms of B count up the number of 1s in A.  Then, the fourth term of B is 1, indicating that the 2 that is the fourth term in A is the first time that a 2 shows up in A.  The fifth term of A is 1, which is the fourth 1 in A, and the fifth term of B is 4, to reflect that.  Likewise, the terms in A count up how many times each number is B has occurred.

All this relates to the image at the top of the page by considering the terms in A and B to be coordinates in the (x, y) plane and drawing segments from one point to the next.  The line begins in one corner, at point (1,1), then continues to (1,2), (1,3), (2,1), etc.  The image at the top has been rotated and flipped for aesthetic considerations; here is a blowup of the beginning of the curve oriented normally so you can follow it from point to point.
This post has been concerned with the principal solution of the quadratic equation, r = (a + sqrt(a2 + 4b))/2.  But there is a second solution, r = (a - sqrt(a2 + 4b))/2.  Here is the image corresponding to those values of r.