How many ways I can permute the $n$ digits binary without counting the neighboring $1$s?

Question

I know it is possible to count the number of reinterpretations of ones and zeros in binary of any given digit using the simple law $2^n$, but I want to remove the duplicate count where $11$, or $111$ is present. Only $1010$, $01$, $0101$ but not $0110$. I mean no double $1$s should neighboring each other. Is there any laws for that?

Answer 1

It follows the Fibonacci sequence, starting with $$2,3,5,8,13,21,\dots$$

To see why, visualize the branching tree of the process. Each $0$ in there gives us two possible continuations, $0$ and $1$, while $1$ only allows $0$ to follow. This is equivalent to the well-known "rabbit-scenario" formulation of the Fibonacci sequence, where a rabbit must mature (go from being a $1$ to being a $0$) before it can reproduce.

Answer 2

Yes it's simple to find that for given length $n$. Let $dp[i][j]$ denote the answer for length $i$ and ending at $j$.
$dp[1][1] = dp[1][0] = 1$.
For $i>1$,
$dp[i][0] = dp[i-1][0]+dp[i-1][1]$
$dp[i][1] = dp[i-1][0]$
Answer would be $dp[n][0]+dp[n][1]$