## Problem of the Day #345: Binary BoundsFebruary 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$?