Question

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$. Which of the following is correct?

• A. $a_{17}=a_{16}+a_{15}$
• B. $c_{17}\ne c_{16}+c_{15}$
• C. $b_{17}\ne b_{16}+c_{16}$
• D. $a_{17}=c_{17}+b_{16}$

Answer 1

The correct option is A $a_{17}=a_{16}+a_{15}$

In such a number either last digit is ${}^{\prime }{0}^{\prime }$ or ${}^{\prime }{1}^{\prime }$
When you consider ${}^{\prime }{a}_1^{\prime }$, only one number is possible i.e. $1$
When you consider ${}^{\prime }{a}_2^{\prime }$, 2 such numbers are possible i.e. $10$, $11$
When you consider ${}^{\prime }{a}_3^{\prime }$, 3 such numbers are possible i.e. $101$, $111$, $110$
When you consider ${}^{\prime }{a}_4^{\prime }$, 5 such numbers are possible i.e. $1010$, $1011$, $1110$, $1101$, $1111$
By observing this we get a relationship which is $a_n$ $=$ $a_{n-1}$ $+$ $a_{n-2}$
So, $a_{17}$ $=$ $a_{16}$ $+$ $a_{15}$

(Alternate Method)

Using Recursion formula

$a_n=a_{n-1}+a_{n-2}$

Similarly, $b_n=b_{n-1}+b_{n-2}$ and $c_n=c_{n-1}+c_{n-2}$ $\forall n\ge 3$

and $a_n=b_n+c_n$ $\forall n\ge 1$

So, $a_1=1,a_2=2,a_3=3,a_4=5,a_5=8$ .......

$b_1=1,b_2=1,b_3=2,b_4=3,b_5=5,b_6=8$ .......

$c_1=0,c_2=1,c_3=1,c_4=2,c_5=3,c_6=5$ .......

Using this we get $b_{n-1}=c_n$

$\therefore a_{17}=a_{16}+a_{15}$