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 the term 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

Hint: According to the question we have to determine the correct expression when 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 the term 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. So, first of all we have to consider the possible number for ${a_1}$ which is only a one digit number.
Now, we have to determine the possible number ${a_2}$which is a two digits number and now same as we have to we have to determine the possible number ${a_3}$which is a three digits number and same as we have to determine the possible number ${a_4}$which is a four digits number.
Now, we have to observe all of the relationships to choose the correct expression.

Complete step-by-step answer:
Step 1: First of all we have to consider whether the last digit is ‘0’ or ‘1’ and when we consider $'{a_1}'$ so there is only one number possible which is 1.
Step 2: Now, same as the step 1 we have to consider $'{a_2}'$ such number and two such possible numbers can be ‘10’ and ’11’
Step 3: Now, when we consider $'{a_3}'$ then three such number are possible can be ‘101’, ‘111’, and ‘110’
Step 4: Now, when we consider $'{a_4}'$ then five such number are possible can be ‘1010’, ‘1011’,’1110’,’1101, and ‘1111’
Step 5: Now, on observing all the steps we get a relationship which is ${a_n} = {a_{n - 1}} + {a_{n - 2}}$ so, on substituting n = 17 in the relationship as obtained,
$
   \Rightarrow {a_{17}} = {a_{17 - 1}} + {a_{17 - 2}} \\
   \Rightarrow {a_{17}} = {a_{16}} + {a_{15}}
 $
Hence, we have obtained the correct relationship which is ${a_{17}} = {a_{16}} + {a_{15}}$.

Therefore our correct option is (A)

Note: Alternative method:
Step 1: First of all we have to use the Recursion formula to obtain the correct expression which is ${a_n} = {a_{n - 1}} + {a_{n - 2}}$ and same as ${b_n} = {b_{n - 1}} + {b_{n - 2}}$ and ${c_n} = {c_{n - 1}} + {c_{n - 2}}\forall n \geqslant 3$
Step 2: So, we can obtain for ${a_1} = 1,{a_2} = 2,{a_3} = 3,$ and ${a_4} = 5$
Step 3: Now, same as the step 2, ${b_1} = 1,{b_2} = 1,{b_3} = 2,$ and ${b_4} = 3$
Step 4: Now, same as the step 3, ${c_1} = 0,{c_2} = 1,{c_3} = 1,$ and ${c_4} = 2$
Step 5: Now, with the help of solutions steps we get ${b_{n - 1}} = {c_n}$. Hence,
$ \Rightarrow $${a_{17}} = {a_{16}} + {a_{15}}$