Let c_n0 be the number of such strings of length n and ending in 0. Likewise c_n1 for those ending in 1. c₁₀ = c₁₁ = 1. By induction if we know c_n0 and c_n1 then c_(n+1)0 = c_n0 + c_n1 for a 0 may be appended to either category of string. But c_(n+1)1 = c_n0 for a 1 may be appended only to strings ending in 0. We have thus by induction c_(n+1)0 = c_n0 + c_(n-1)0 which is the defining equation from Fibonacci.

This technique can be carried out for any sort of local constraint. It will generally lead to an exponentially increasing count. For Fibonacci we can guess that F_i = e^αi and get e^α(i+1) = e^αi + e^α(i−1) or dividing by e^αi we get e^α = 1 + e^−α or e^α = 1 + 1/e^α whence e^α = (√5+1)/2. The Fibonacci terms indeed increase roughly exponentially.

See this for a generalization to 2D.