Let $A_n$ denote the number of all $n$-digit positive integers formed by the digits $0,1$ or both such that no consecutive digits in them are $0$. Let $B_n$ the number of such $n$-digits integers ending with digit $1$ and $C_n$ the number of such $n$-digit integers ending with digit $0$. The value of $B_6$ is?
I have no idea what this is all about, but my books says this is Fibonacci series in disguise.
On
If you never can have two consecutive $0$'s, one gets the following recursions: $$B_n = B_{n-1}+C_{n-1}$$ $$C_n = B_{n-1}$$ The first one is because an $n$ digit number ending in $1$ is formed by an $n-1$ digit number followed by the digit $1$. The number of $n-1$ digit numbers is simply $B_{n-1}+C_{n-1}$. The second one is because you can't have two consecutive $0$'s, so the $n-1$ first digits of an $n$ digit number ending in $0$, have to end in $1$, which can be done in $B_{n-1}$ ways. Combining the two gives $$B_n = B_{n-1}+B_{n-2}.$$ We also have $B_1=1$ and $B_2=2$, so it is clear that $B_n$ simply are the fibonacci numbers (you can define $B_0=1$). Then $B_6=13$.
Edit: given that the first digit must be $1$, this gives $B_1=1$ and $B_2=1$, such that $B_6=8$ instead (Fibonacci number $5$). The recursions still hold.
Hint: Suppose you have some element of $B_n$. What can you say about the first $n-1$ digits as they relate to $A_{n-1}$? Now how about if you have an element of $C_n$? (Here you may end up looking at $A_{n-2}$.)