The relationship between Fibonacci numbers and binary numbers that have no consecutive zeroes

Question

I know it is the Fibonacci recurrence relation and I looked at these two posts.

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

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

But I don't understand how i can apply it to this particular problem.

How do i know what all the 9 digit binary numbers are and how many of them do not contain consecutive zeros? How would i do it for 12 digit binary numbers?

Answer 1

Facts:

1. Denote $a(n)$ the function that counts the number of binary strings without 2 consecutive 0's. $$a(1)=2$$ $$a(2)=3$$
2. Fibonacci sequence is defined as such: $$f(0)=0,\;f(1)=1,\;f(2)=1$$ $$f(n)=f(n-1)+f(n-2)$$ $$f(3)=2,\;f(4)=3$$
3. Obviously, $a(n)=f(n+2)$, why? Since $a(1)=f(1+2)=2$
4. Therefore, this come down to finding the closed form of $f(n+2)$ for Fibonacci sequence.

Solution technique:

1. Establish the characteristics equation and its roots. $$r^2-r-1=0$$ $$r=\frac{1\pm\sqrt5}{2}$$
2. Assume $f_n=c_1r_1^n+c_2r_2^n$, where $r_1$ and $r_2$ are distinct roots in this case.
3. Find $c_1,\;c_2$ $$r_1=\frac{1+\sqrt5}{2},\;r_2=\frac{1-\sqrt5}{2}$$ $$f_0=c_1r_1^0+c_2r_2^0=c_1+c_2=0$$ $$f_1=c_1r_1^1+c_2r_2^1=c_1r_1+c_2r_2=1$$ $$\left[\begin{array}{cc|c}1&1&0\\\frac{1+\sqrt5}{2}&\frac{1-\sqrt5}{2}&1\end{array}\right]=\cdots=\left[\begin{array}{cc|c}1&0&\frac{1}{\sqrt5}\\0&1&-\frac{1}{\sqrt5}\end{array}\right] $$

Therefore, the closed form of $a(n)$ is:

$$a(n)=f(n+2)=\frac{1}{\sqrt5}(\frac{1+\sqrt5}{2})^{n+2}-\frac{1}{\sqrt5}(\frac{1-\sqrt5}{2})^{n+2}$$

How many possible 9-bits strings?

$2^9$

How many of 9-bits strings do not contain consecutive zeros?

$$a(9)=f(11)=\frac{1}{\sqrt5}(\frac{1+\sqrt5}{2})^{11}-\frac{1}{\sqrt5}(\frac{1-\sqrt5}{2})^{11}$$