# How many length n binary numbers have no consecutive zeroes ?Why we get a Fibonacci pattern?

Possible Duplicate:
How many $N$ digits binary numbers can be formed where $0$ is not repeated

I am really embarrassed to ask this as it seems like a textbook question.But it is not, and I am at a complete loss how to get a grip on it.It is mentioned in the first lecture of a 24 lecture series on Discrete Mathematics by the popular Mr.Arthur Benjamin(Discrete Mathematics-The Great Courses),which I am following.He only fleetingly mentions that we use combinatorics to solve this and starting with n=1 (1 bit number), the answer follows the Fibonacci pattern 2,3,5,8……So please answer this for me lest I get discouraged from the start of the subject itself.

i)If we are asked to find the number of n-length binary numbers with no consecutive zeroes,then how do we go about it?I have a fair idea about combinatorics,binary coefficients,permutations, yet I just can’t figure how to start.So what is the logic we use?

ii)Why does it follow a Fibonacci pattern for n,n+1,n+2 and so on?This further bewilders me.Why on earth is a Fibonacci pattern generated?There must be an explanation…

Your clear and easy-to-understand answers will go a long way in motivating me further into the subject.Thanks!

#### Solutions Collecting From Web of "How many length n binary numbers have no consecutive zeroes ?Why we get a Fibonacci pattern?"

Consider the length $n$ binary strings with no repeated zeros (BSWNRZ).

BSWNRZ must end in a $0$ or a $1$. The number of BSWNRZ of length $n$ that end in a $0$ is equal to the number of BSWNRZ of length $n-2$ (with $10$ appended). The number of BSWNRZ of length $n$ that end in a $1$ is equal to the number of BSWNRZ of length $n-1$ (with $1$ appended).

That is, any length $n$ BSWNRZ falls into one of the following two cases

$$\overbrace{?????????????????}^{\text{any length }n-2\text{ BSWNRZ}}\color{#00A000}{1}\color{#C00000}{0}\\ \underbrace{??????????????????}_{\text{any length }n-1\text{ BSWNRZ}}\color{#C00000}{1}$$

Therefore, the number of BSWNRZ of length $n$ is equal to the number of BSWNRZ of length $n-1$ plus the number of BSWNRZ of length $n-2$. Thus, the Fibonacci pattern.
$$F_n=F_{n-1}+F_{n-2}$$