Let $a_n$ denote the number of $n$-digit binary numbers such that no two zeroes are consecutive. Is $a_{17}=a_{16}+a_{15}$?
Let $a_n$ denote the number of $n$-digit binary numbers such that no two zeroes are consecutive.
$$a_1=2$$ $$a_2=3$$ $a_3$ can contain one $1$, two $1$s or all $1$s.
$$a_3=1+\frac{3!}{2!}+1=5$$ $$a_4=0+3+4=7$$ $$a_5=0+0+6+5+1=12$$
I don't see any relation connecting the above $a_i$s. The number of possibilities depend on the number of $1$s. Should I calculate $a_n$?
On
To see the recursion you want: Let $b_n$ be the number of such sequences that end in $0$, and $c_n$ the number that end in $1$. We have $$a_n=b_n+c_n$$
It is easy to see that $$c_n=a_{n-1}\;\;\&\;\;b_n=c_{n-1}\implies b_n=a_{n-2}$$
On
$a_n$ number of n-digit binary numbers with no two consecutive 0s, which start with 1
$b_n$ number of n-digit binary numbers with no two consecutive 0s, which start with 0
Then:
$a_n = b_{n-1} + a_{n-1}$
$b_n = a_{n-1}$
Try to prove why these are true.
So it leads to a recursion on two sequences (very nice).
Let $a_n$ be the number of $n$-digit binary numbers such that no two zeroes are consecutive.
Consider the last digit of the $n$-digit binary number.
Case 1: The last digit is $1$
In this case, the first $n-1$ digits must satisfy the condition that no two zeroes are consecutive. There are $a_{n-1}$ ways in which they can do so, thus the total number of $n$-digit binary numbers with no two zeroes consecutive and ending with $1$ is $a_{n-1}$.
Case 2: The last digit is $0$
In this case, the last but one digit cannot be zero, as it would violate the given condition. Thus, the last but one digit must be $1$. There are now $a_{n-2}$ ways in which the first $n-2$ digits can satisfy the given condition. Thus, the number of $n$-digit binary numbers with no two zeroes consecutive and ending with $0$ is $a_{n-2}$.
This thus gives the recurrence relation, $$a_n=a_{n-1}+a_{n-2}$$ It is easy to verify that $a_0=1,a_1=2$, which are the base cases.