A054770

[John Conway]

On Thu, 8 Jun 2000, Jud McCranie wrote:

> Also, I got the impression that the way the Lucas numbers are defined as 
> they are is because they are the simplest such sequence that gives a 
> sequence distinct from the Fibonacci numbers.  Starting with 1,2 just gives 
> the Fibonacci numbers shifted by one place, so that isn't interesting.  The 
> next case is 1,3; which gives a sequence distinct from the Fibonacci 
> sequence.  That, to me, seems like a justification for starting the Lucas 
> numbers at 1 - if that is clearly stated.

   This brings to mind Kimberling's wonderful and little-known theory
about the entire set of Fibonacci-like sequences, which is much more
interesting than discussing where they should properly start.

   So let me describe this theory (in my own language, rather than
Kimberling's).  It leads to a table:

        -1  0| 1  2  3  4  5  6  7  8  9 10 ...
         ----+---------------------------------
         0  1| 1  2  3  5  8 13 21 34 55 89 ...
         1  3| 4  7 11 18 29 47 76 ...
         2  4| 6 10 16 26 42 68 ...
         3  6| 9 15 24 39 63 ...
         4  8|12 20 32 52 84 ...
         5  9|14 23 37 60 97 ...
         6 11|17 28 45 73 ...
         7 12|19 31 50 81 ...
         8 14|22 36 58 94 ...
         9 16|25 41 66 ...
        10 17|27 44 71 ...
         ...........

which includes (suitable tails of) all such sequences.  Now this
theory does express an opinion as to where these start - let's 
say that they do so just to the right of the vertical bar,
because with this convention each positive integer belongs to just
one such sequence.  The sequence of numbers that tells you just
which, I call "the paraFibonacci sequence"

      n :  1 2 3 4 5 6 7 8 9  11  13  15  17  19  21  23  25  
paraFib :  0 0 0 1 0 2 1 0 3 2 1 4 0 5 3 3 6 3 7 4 0 8 5 3 9 2 

because it tells you the "parameter" (as given in the -1 column)
of the first Fibonacci-like series to which it belongs.  This is
0 for Fibonacci numbers themselves,  1 for Lucas numbers that aren't
Fibs, 2,3,4 for the remaining doubles, trebles and quadruples of Fibs,
and so on.

   The rule for continuing this table is very simple : to start row
number  n,  you find  n  in the main table (to the right of the bar)
and follow it in its own row by the successor of the number that appears
there.  So for instance the number 11 is followed in row 11 by 19, 
since it was followed in row  1  by  18.  The first row I didn't 
print is therefore

        11 19|30 49 79 ... .

   The table has lots of other fascinating properties, which I'll 
leave you all to discover, hoping that some of you will even find 
some new ones.  I think it's the most interesting thing about the
Fibonacci numbers to have been discovered in the 20th century!

   John Conway