We have a calculator with two buttons that displays an integer . Pressing the first button replaces by , and pressing the second button replaces by . Initially, the calculator displays 0. How many integers less than or equal to 2014 can be achieved through a sequence of arbitrary button presses? (It is permitted for the number displayed to exceed 2014 during the sequence. Here, denotes the greatest integer less than or equal to the real number .)
Solution
We consider the integers from this process written in binary. The first operation truncates the rightmost digit, while the second operation appends 01 to the right. We cannot have a number with a substring 11. For simplicity, call a string valid if it has no consecutive . Note that any number generated by this process is valid, as truncating the rightmost digit and appending 01 to the right of the digits clearly preserve validity. Since we can effectively append a zero by applying the second operation and then the first operation, we see that we can achieve all valid strings. Note that 2014 has eleven digits when written in binary, and any valid binary string with eleven digits is at most . Therefore, our problem reduces to finding the number of eleven-digit valid strings. Let denote the number of valid strings of length . For any valid string of length , we can create a valid string of length by appending a 0, or we can create a valid string of length by appending 01. This process is clearly reversible, so our recursion is given by , with . This yields a sequence of Fibonacci numbers starting from 2, and some computation shows that our answer is .