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!