Binary Strings Without Odd Runs of Zeros

Abstract

We look at binary strings of length \(n\) which contain no odd run of zeros and express the total number of such strings, the number of zeros, the number of ones, the total number of runs, and the number of levels, rises, and drops as functions of the Fibonacci and Lucas numbers and also give their generating functions. Furthermore, we look at the decimal value of the sum of all binary strings of length \(n\) without odd runs of zeros considered as base \(2\) representations of decimal numbers, which interestingly enough are congruent (mod \(3\)) to either \(0\) or a particular Fibonacci number. We investigate the same questions for palindromic binary strings with no odd runs of zeros and obtain similar results, which generally have different forms for odd and even values of \(n\).