+31 A fibbinary number is a number whose binary representation contains no consecutive \(1\)s.
Prove that the number of non-negative fibbinary numbers less than or equal to \(2^n\) is always \(\text{Fib}_{n+1} + 1\).
Have fun with this interesting problem!
+506 It's indeed an interesting problem.
The proof here is based on the brick wall problem in the picture below (the proof is quite simple and it involves some simple induction)
Rephrasing this problem, it basically asks for the proof that the number of ways to have n-1 digits, each one of them either 1 or 0, without having consecutive 1's, is equal to the n+1th Fibonacci number. (2^n will always be a fibbinary number, so we can add 1)
Other than the rightmost digit, a 1 must be followed by a 0, so we can group them together as '10', or a block of length 2, and the other zeroes other than the rightmost digit can be treated as a block of length 1.
If the last digit is a 1, then the number of possibilities is equal to that of a brick wall of length n-2. If the last digit is a zero, then the number of possibilities is equal to that of a brick wall of length n-1.
As mentioned before, this proof is based on the brick wall problem, so they are equal to the n-1th and nth Fibonacci numbers, respectively.
I think you can finish it
