Solveeit Logo
Login

Question

Question: Let \({a_n}\) denote the number of all n-digit positive integers formed by the digits 0, 1 or both s...

Let an{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 bn={b_n} = the number of such n-digit integers ending with digit 1 and cn{c_n}= the number of such n-digit integers ending with digit 0. Which of the following is correct?
A) a17=a16+a15{a_{17}} = {a_{16}} + {a_{15}}
B) c17≠c16+c15{c_{17}} \ne {c_{16}} + {c_{15}}
C) b17≠b16+c16{b_{17}} \ne {b_{16}} + {c_{16}}
D) a17=c17+b16{a_{17}} = {c_{17}} + {b_{16}}

Explanation

Solution

According to the question we have to determine the correct expression when let an{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 bn={b_n} = the number of such n-digit integers ending with digit 1 and cn{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 a1{a_1} which is only a one digit number.
Now, we have to determine the possible number a2{a_2}which is a two digits number and now same as we have to we have to determine the possible number a3{a_3}which is a three digits number and same as we have to determine the possible number a4{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 ′a1′'{a_1}' so there is only one number possible which is 1.
Step 2: Now, same as the step 1 we have to consider ′a2′'{a_2}' such number and two such possible numbers can be ‘10’ and ’11’
Step 3: Now, when we consider ′a3′'{a_3}' then three such number are possible can be ‘101’, ‘111’, and ‘110’
Step 4: Now, when we consider ′a4′'{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 an=an−1+an−2{a_n} = {a_{n - 1}} + {a_{n - 2}} so, on substituting n = 17 in the relationship as obtained,
⇒a17=a17−1+a17−2 ⇒a17=a16+a15 \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 a17=a16+a15{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 an=an−1+an−2{a_n} = {a_{n - 1}} + {a_{n - 2}} and same as bn=bn−1+bn−2{b_n} = {b_{n - 1}} + {b_{n - 2}} and cn=cn−1+cn−2∀n⩾3{c_n} = {c_{n - 1}} + {c_{n - 2}}\forall n \geqslant 3
Step 2: So, we can obtain for a1=1,a2=2,a3=3,{a_1} = 1,{a_2} = 2,{a_3} = 3, and a4=5{a_4} = 5
Step 3: Now, same as the step 2, b1=1,b2=1,b3=2,{b_1} = 1,{b_2} = 1,{b_3} = 2, and b4=3{b_4} = 3
Step 4: Now, same as the step 3, c1=0,c2=1,c3=1,{c_1} = 0,{c_2} = 1,{c_3} = 1, and c4=2{c_4} = 2
Step 5: Now, with the help of solutions steps we get bn−1=cn{b_{n - 1}} = {c_n}. Hence,
⇒\Rightarrow a17=a16+a15{a_{17}} = {a_{16}} + {a_{15}}