## Problem of the Day #345: Binary Bounds
*February 27, 2012*

*Posted by Saketh in : potd , trackback*

Gillie is counting certain binary strings. He defines $f(n,k)$ to be the number of binary strings of length $n$ that do not contain any substring of $k$ consecutive zeroes or ones.

Let $a(k)$ be the greatest real number such that $f(n,k) \geq a(k)^n$ for every positive integer $n$. Find $a(6)$.

**Bonus:** How does $a(n)$ behave in the general case? Is it possible to express $a(n)$ as an elementary function of $n$?

## Comments»

False. Gillie is extremely allergic to binary strings and racism. This problem DNE.