Tags

,

Anyone reading this is surely familiar with the Fibonacci numbers, that very famous sequence defined by the recurrence:

\text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)

with:

\text{fib}(0) = 1 \text{, and fib}(1) = 1.

And though it’s not typical, for our purposes here it will be convenient to redefine the sequence so that:

\text{fib}(0) = 1 \text{ and fib}(1) = 2.

Using this later definition, which is simply a shift by one place, it can be shown for n>0 that the nth Fibonacci number corresponds to the number of bit strings of length n that do not contain the sub-string “11”. Thus the number of bits strings of length n that do contain the sub-string “11” is:

2^n - \text{fib}(n).

We can also define a Fibonacci-like sequence with three terms as follows:

\text{fib}_3(n) = \text{fib}_3(n-1)+ \text{fib}_3(n-2) + \text{fib}_3(n-3)

with:

\text{fib}_3(0)=1, \text{fib}_3(1) =2 \text{,and fib}_3(2) = 4.

And in general this notion can be extended to a k-term, or rather k-step, sequence where:

\displaystyle \text{fib}_k(n) = \sum^k_{i=1} \text{fib}_k(n-i)

See Wolfram Math World’s great explanation for more about this, although they obviously do not shift the sequences as we have done here. Notice however, that when shifted, the k-step Fibonacci sequences presented at Math World begin with the sub-sequence:

(1,2,4,...)=(2^0, 2^1, ..., 2^{k-1})

To generalize our bit string example from before, it can be observed that the nth term of the k-step Fibonacci sequence corresponds to the number of bit strings of length n that do not contain a sub-string of length k that is composed of all ones.

The Fibonacci numbers can be further generalized by introducing a scaling factor m, where we define:

\displaystyle \text{fib}_{k,m}(n) = (m-1)\sum^k_{i=1} \text{fib}_{k,m}(n-i)

where the initial elements of the sequence fibk,m are:

(m^0, m^1, ..., m^{k-1})

And thus:

\text{fib}_{2,2}(n)

corresponds to the regular old Fibonacci numbers.

It turns out that the nth term of fibk,m corresponds to the number of strings of length n using an alphabet of size m that do not have a sub-string of k consecutive ones, assuming of course that the character “1” is part of the alphabet. Conversely, the number of strings that do contain such a sub-string is equal to:

m^n - \text{fib}_{k,m}(n)

For example see OEIS sequence A028859 and A119826, which correspond to fib2,3 and fib3,3 respectively.

Another interesting bit about all of this concerns the the limit of fibk,m(n+1)/fibk,m(n) as n goes to infinity. Here again fib2,2 has a special place as:

\displaystyle \lim_{n \rightarrow \inf} \frac{\text{fib}_{2,2}(n+1)}{\text{fib}_{2,2}(n)} = \varphi

where φ is the Golden Ratio, one of the more interesting irrational numbers. It is also a root of the polynomial:

f(x)=x^2-x-1

More generally:

\displaystyle \lim_{n \rightarrow \inf} \frac{\text{fib}_{k,m}(n+1)}{\text{fib}_{k,m}(n)}

is a root of the polynomial:

\displaystyle f(x)=x^k - (m-1) \sum^{k-1}_{i=0} x^i.

Here is some Python code for playing with all of this.

#!/usr/bin/python

import re
import itertools

def i2bs(i, l, m):
    """
    Convert an incoming number into a 'bitstring' representation
    of length 'l' using an alphabet of size 'm'. This behavior of
    this function is undefined if m>10.
    """
    i = int(i)
    out = ""
    while i:
        out = str(i%m) + out
        i /= m
    delta = l - len(out)
    if delta > 0:
        out = ("0" * delta) + out
    return out

def fib(n, k=2, m=2):
    """
    Generate the nth k-step, m-scale fibonacci number. 

    n specifies which index in the sequence to generate. (length of the over all string)
    k specifies how many terms the recurrence has (length of the subsequence we are searching)
    m is the factor that each term of the reccurrence is multiplied by plus 1 (size of alphabet)

    The output is the nth number in the sequence, which is also equal to the number of
    times the subsequence "1"*k appears in the permutations of length n over the alphabet.
    """
    f = [pow(m,i) for i in range(k)]
    if n < len(f):
        return f[n]
    i=k
    while i < n:
        f[i%k]=sum(f)*(m-1)
        i+=1
    return sum(f)*(m-1)

def matchbits(k,m):
    """
    This function allows us to play with the proposition that fib(n,k,m) is the number
    of substrings "1"*k in the permutations of length n over an alphabet of size m.

    k is the size of substring to match
    m is the size of the alphabet
    """
    print("***",k,m)
    ss=k*"1"

    for n in range(k,10):
        matches=0
        total=pow(m,n)
        for i in range(total):
            x = i2bs(i,n,m)
            if re.search(ss,x):
                matches += 1

        f =fib(n,k,m)
        print(("Subsequence=%s, Actual Matches=%d, Predicted Matches=%d, Okay=%s") %
              (ss, matches, total-f, ((total-f)== matches)))

def poly(k,m,x):
    """
    Evaluate the polynomial f(x) = x^k - (m-1)*x^(k-1) - ... - (m-1)
    """
    return x**k + sum([-(m-1)*x**i for i in range(k)])

def checkroots(n, coefficients):
    """
    Allows us to play with the polynomials of which fib(n+1, k, m)/fib(n, k, m)  is a root.
    """
    for (k,m) in itertools.product(coefficients, coefficients):
        fn = fib(n,k,m)
        fn1 = fib(n+1,k,m)
        x=float(fn1)/float(fn)
        print("k=%d, m=%d, x=%f, f(x)=%f") % (k, m, x, poly(k,m, x))

def main():
    print("Check Roots")
    checkroots(100, [2,3,4,5])

    print("\n")

    print("Match Bits:")
    matchbits(2,2)
    #matchbits(3,2)
    #matchbits(3,4)
    #matchbits(5,4)

if __name__ == "__main__":
    main();
Advertisements