Fibonacci, 1/89, And All That

One of the most frequently re-discovered facts about the Fibonacci
numbers 0,1,1,2,3,5,8,13,21,34,... is that if we tabulate these
numbers in a column, shifting the decimal point one place to the
right for each successive number, the sum equals 1/89, as indicated
below:
             .0
             .01
             .001
             .0002
             .00003
             .000005
             .0000008
             .00000013
             .000000021
             .0000000034
                 etc.
            ----------------
             .01123595505618...  =  1/89

This is fairly trivial to prove, but it's an instance of an interesting
general pattern involving geometrically weighted sums of the terms of 
arbitrary linear recurring sequences.  In the simple case of Fibonacci 
numbers, or, a bit more generally, any monic second-order recurrence 
relation
                s[n] = a s[n-1] + b s[n-2]

the characteristic polynomial is

                 f(x)  =  x^2 - ax - b

with the two (assumed distinct) roots
                  __________                  __________
             a + / a^2 + 4b              a - / a^2 + 4b
      r1  =  ---------------      r2  =  ---------------
                    2                            2

It follows that, for the initial values s[0]=0, s[1]=1, the nth term
of the recurring sequence is

                      1     /   n       n \
          s[n]  =  ------- (  r1   +  r2   )
                   sqrt(D)  \             /

where D is the discriminant a^2 - 4b.  The tabular summation described
above, generalized to the base B, then consists of the terms

               s[0]   s[1]   s[2]              1  oo  s[n]
        S  =   ---- + ---- + ---- + ....   =   - SUM  -----
                 B     B^2    B^3              B  n=0  B^n

Substituting the previous expression for s[n] and collecting terms,
we have         
                1      /  oo        n       oo        n \
      S  =  --------- (  SUM  (r1/B)   -   SUM  (r2/B)   )
            B sqrt(D)  \  n=0               n=0         /

If the geometric sums converge, (meaning that the roots with the
largest magnitude is smaller than the base B), then we can write
the sums in closed form

                  1      /    1            1     \
        S  =  --------- (  --------  -  --------  )
              B sqrt(D)  \ 1 - r1/B     1 - r2/B /


                  1     /   1          1    \
           =   ------- (  ------  -  ------  )
               sqrt(D)  \ B - r1     B - r2 /


                 1     /    r1 - r2   \
           =  ------- (  ------------  )
              sqrt(D)  \ (B-r1)(B-r2) /

Since r1 - r2 equals sqrt(D), and noting that the denominator in the
parentheses is f(B), because it is the product of terms of the form
B minus each root of f, we can multiply S by B and write the sum

                 oo  s[n]         B
       SB   =   SUM  -----   =   ----
                 n=0  B^n        f(B)

Now, for the Fibonacci numbers the characteristic polynomial is
f(x) x^2 - x - 1, so the sum S for the base 10 is given by setting
B=10, which gives S = 1/f(10) = 1/89.

It can be shown that this same summation applies to any (convergent)
linear recurring sequence with the initial values 0,0,..,0,1,... 
(assuming the characteristic polynomial has distinct roots).  For
example, the sequence that satisfies the 3rd order relation

          s[n] = 3s[n-1] - 5s[n-2] + 7s[n-3]

consists of the values

                0,0,1,3,4,4,13,47,...

and the characteristic polynomial is

             f(x) = x^3 - 3x^2 + 5x - 7

As can easily be verified, the sum of the terms of this sequence,
written in base 10, arranged in a column with the decimal point 
shifted to the right for each successive number (as illustrated 
above for the Fibonacci numbers) is 

      S  =  1/f(10)  =  1/(1000-300+50-7)   =   1 / 743

This places the familiar "1/89" aspect of the Fibonacci numbers in
perspective, and shows that it's just one special case of of much
more general result.

This can be seen as a generalization of the simple geometric sum,
because if we define the 1st-order recurring sequence by s[0]=1 
and s[k] = a s[k-1] then we have s[n] = a^n, and the characteristic
polynomial is f(x) = x - a.  So, the general formula reduces to the
familiar sum

            oo   a^n         B            1
           SUM   ---   =   -----   =   --------
            n=0  B^n       B - a       1 - (a/B)

So far we have considered only recurrences with the initial values
0,0,..,0,1, but we can also generalize to any set of initial values
s0,s1,..,s(N-1) for an Nth-order recurrence.  Let's write the general
characteristic polynomial as

       f(x) = x^N - c_1 x^(N-1) - c_2 x^(N-2) - ... - c_N

and then, calling this f_0(x), let's define the sequence of polynomials
f_j(x) for j=1,2,... as follows

                       f_j(x) + c_(N-j)
        f_{j+1}(x)  =  ----------------
                              x

For example, if f(x) = x^3 - ax^2 - bx - c then we have

        f_0(x)  =  x^3 - ax^2 - bx - c

        f_1(x)  =  x^2 - ax  -  b

        f_2(x)  =  x  -  a

        f_3(x)  =  1

In these terms we can write the sum of s[n]/B^n for n=0 to infinity
for any arbitrary linear recurrence (with distinct characteristic
roots) and any initial values s[0], s[1],.., s[N-1] as

   oo  s[n]         f_1(B) s[0] + f_2(B) s[1] + ... + s[N-1]
  SUM  -----   =  B ----------------------------------------
   n=0  B^n                           f(B)

Of course, in our previous considerations we had s[0], s[1], ..,s[N-2]
all equal to zero, and s[N-1] equal to 1, so this reduced to B/f(B).
In general we see that the sum equals a linear function of the N
initial values, where the kth initial value has a coefficient of
B f_{k+1}(B)/f_0(B).  In the special case of sequences that satisfy
the Fibonacci recurrence s[n]=s[n-1]+s[n-2] beginning with the
arbitrary initial values s[0] and s[1], the sum is given by
[(B-1)s[0] + s[1]] / 89.