Prove that the number of binary strings of length n with no

Prove that the number of binary strings of length n with no two consecutive 0s is given the Fibonacci sequence term F(n + 2).

Solution

Answer :

Let F(n) be the number of bit strings of length n which contain no substring 00. Split such bit strings into two groups, those that end in 1 and those that end in 0.

The first group has F(n-1) bit strings with no substring 00, and the second group has F(n-2) bit strings with no substring 00 because the second last bit must be a 1.

Thus F(n) = F(n-1) + F(n-2), n > 2. This work shows that B(1) = 2 and B(2) = 3.

or replace n by n + 2

we get F(n + 2) = F(n + 1) + F(n), n > 0. This work shows that F(1) = 2 and F(2) = 3.