Let $a_{n}$ denote the number of all $n$-digit positive integers formed by the digits 0,1 or both such that…
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$-digit integers ending with digit 1 and $c_{n}=$ the number of such $n$-digit integers ending with digit 0 .
Question: The value of $b_{6}$ is
7
8
9
11
Solution
$\because a_{n}=$ number of all $n$ digit +ve integers formed by the digits 0,1 or both such that no consecutive digits in them are 0 .
and $b_{n}=$ number of such $n$ digit integers ending with 1 $c_{n}=$ number of such $n$ digit integers ending with 0
Clearly, $a_{n}=b_{n}+c_{n}\left(\because a_{n}\right.$ can end with 0 or 1)
Also $b_{n}=a_{n-1}$ and $c_{n}=a_{n-2}[\because$ if last digit is 0 , second last has to be 1]
$\therefore$ We get $a_{n}=a_{n-1}+a_{n-2}, n \geq 3$
Also $a_{1}=1, a_{2}=2$,
Now by this recurring formula, we get
$\begin{aligned} a_{3} &=a_{2}+a_{1}=3 \\ a_{4} &=a_{3}+a_{2}=3+2=5 \\ a_{5} &=a_{4}+a_{3}=5+3=8 \\ \text { Also } b_{6} &=a_{5}=8 \end{aligned}$