I am solving a problem which asks: How many $13$-bit binary numbers that have no two $0$'s together are there?
My first approach: A $13$-bit binary number can
either start and end with $0$ like $0101010101010$ and here we can replace the $0$'s with $1$ also that is they have two choices either be $0$ or $1,$ therefore for seven $0$'s, $2^7$ choices;
or start and end with $1$ so for six $0$'s, $2^6$ choices.
Therefore, the solution is $2^7 + 2^6 -1=191.\;$ ($-1$ so that $13$-bit binary number with all $1$'s is considered only once.)
My second approach, using recurrence relation for $n$-bit binary numbers with no two consecutive $0$'s: $$a_{n} = a_{n-1} + a_{n-2}, a_0 = 1, a_1 = 2, a_2 = 3$$ so for $a_{13}$ the answer is $610.$
Here is a neat way to think about this problem.
Instead of asking how many 13-bit binary numbers there are with no consecutive 0's we can equivalently ask how many 13-bit binary numbers there are with no consecutive 1's.
In the following we define the Fibonacci numbers as $F_{-1}=1$, $F_0 = 1$, $F_1 = 2$, $F_n = F_{n-1} + F_{n-2}$ (we care for this exact indexation).
A beautiful theorem by Zeckendorf says that every number $n$ can be uniquely decomposed into a sum of pairwise non-consecutive Fibonacci numbers, i.e. $n=\sum_{i=0}^\infty a_i F_i$ with $a_i\in \{0,1\}$ and $a_ia_{i+1}=0$ for all $i$. Taking these coefficients we can turn each number $n$ into a binary string $[n]_Z=a_ka_{k-1}\ldots a_1a_0$, where $k$ is the highest non-zero coefficient (i.e. forget all leading 0's). Let us call $[n]_Z$ the Zeckendorf code of $n$.
One quickly sees that the number of $k$-bit Zeckendorf codes is exactly $F_{k-2}$. Note that all $k$-bit Zeckendorf codes start with 10, so the number of $(k+2)$-bit Zeckendorf codes is exactly the number of $k$-bit binary codes with no consecutive 1's (including those with leading 0's).
Hence, the number of $k$-bit binary codes with no consecutive 1's is $F_k$, in particular, for $k=13$ we get $F_{13}=610$.
I know that this approach is a little overkill for the problem at hand but I wanted to point out the nice mathematics connected to this. Also, there is a generalization of Zeckendorfs theorem for Narayana numbers and all the other higher-order generalized Fibonacci numbers, so that questions like How many binary numbers with all 1's at least $r$ 0's apart are there? can be answered analogously.