Hint: Imagine that we have $13$ "digits," the usual $0$ to $9$, and in addition the digits $\alpha$, $\beta$, $\gamma$, to be thought of as representing $10$, $11$, and $12$ respectively.
Pick a strictly descending sequence $x_1, x_2, x_3, x_4$ of length $4$ from this new digit set of $13$ digits. You know how to count how many such strictly descending sequences there are.
Let $a_4=x_4$, $a_3=x_3-1$, $a_2=x_2-2$, $a_1=x_1-3$. Show that this produces every non-increasing sequence $a_1\ge a_2 \ge a_3 \ge a_4$ in one and only one way.
Now we need to adjust for the unpleasant fact that the initial digit of a $4$-digit number cannot be $0$. That translates into the fact that the strictly descending sequence $x_1=3$, $x_2=2$, $x_3=1$, $x_4=0$ is not allowed.
Remark: The above procedure has nothing much to do with digits. The number of never increasing sequences of length $k$ from the set $\{1,2,\dots,n\}$ is the same as the number of strictly decreasing sequences of length $k$ from the set $\{1,2,\dots,n,n+1,\dots, n+k-1\}$.
Added: The number of strictly decreasing sequences of length $4$ from the digits $0, 1,\dots, 9$ is just $\binom{10}{4}$, the number of ways to choose $4$ distinct numbers. If we use the "digits" $0,1,\dots,9,\alpha,\beta,\gamma$, then the number of strictly decreasing sequences is $\binom{12}{4}$. We must subtract $1$ because $3,2,1,0$ is not allowed.
The binary sequences of length $n$ can only be formed by
- Preceding a length $n-1$ sequence with a $0$
- Preceding a length $n-2$ sequence with $10$ or $11$ such that the second digit matches the third digit of the new sequence. E.g. $000\mapsto \boxed{10}000$ and $100\mapsto \boxed{11}100$.
- Preceding a length $n-4$ sequence with $1100$
Hence we have the recurrence
$$a_n=a_{n-1}+a_{n-2}+a_{n-4}$$
which gives
$$a_n=2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897,\dots$$
Best Answer
Let $a_n$ be the number of $n$-digit binary numbers such that no two zeroes are consecutive.
Consider the last digit of the $n$-digit binary number.
Case 1: The last digit is $1$
In this case, the first $n-1$ digits must satisfy the condition that no two zeroes are consecutive. There are $a_{n-1}$ ways in which they can do so, thus the total number of $n$-digit binary numbers with no two zeroes consecutive and ending with $1$ is $a_{n-1}$.
Case 2: The last digit is $0$
In this case, the last but one digit cannot be zero, as it would violate the given condition. Thus, the last but one digit must be $1$. There are now $a_{n-2}$ ways in which the first $n-2$ digits can satisfy the given condition. Thus, the number of $n$-digit binary numbers with no two zeroes consecutive and ending with $0$ is $a_{n-2}$.
This thus gives the recurrence relation, $$a_n=a_{n-1}+a_{n-2}$$ It is easy to verify that $a_0=1,a_1=2$, which are the base cases.