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

with:

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

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:*

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

with:

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

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:

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:

where the initial elements of the sequence *fib _{k,m}* are:

And thus:

corresponds to the regular old Fibonacci numbers.

It turns out that the *nth *term of *fib _{k,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:

For example see OEIS sequence A028859 and A119826, which correspond to *fib _{2,3}*and

*fib*respectively

_{3,3}*.*

Another interesting bit about all of this concerns the the limit of *fib _{k,m}(n+1)/fib_{k,m}(n)* as n goes to infinity. Here again

*fib*has a special place as:

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

More generally:

is a root of the polynomial:

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();