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}$

Explanation for the correct option:

Determining the correct option:

According to given data

Such number has either the last digit as ′$0$′ or ′$1$′

If we consider ′$a_1$′​, then only one number is possible i.e. $1$

If we consider ′$a_2$′​, then $2$ such numbers are possible i.e. $10,11$

If we consider ′$a_3$′​, then $3$ such numbers are possible i.e. $101,111,110$

If we consider ′$a_4$'​, then $5$ such numbers are possible i.e. $1010,1011,1110,1101,1111$

By observing these numbers we get a relation between them as follows

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

​So, putting $n=17$

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

Similarly Using Recursion formula we have

$b_n=b_{n-1}+b_{n-2}$ and $c_n=c_{n-1}+c_{n-2}$ also,

$a_n=b_n+c_n$

Explanation for the correct options:

So, we have $c_{17}\ne c_{16}+c_{15}$ option (B) is incorrect because $c_{17}=c_{16}+c_{15}$

Since, $b_{n-1}=c_n$ so, $b_{17}\ne b_{16}+c_{16}$ option (C) is incorrect because $b_{17}=b_{16}+c_{16}$

and $a_{17}=c_{17}+b_{16}$ is incorrect because $a_{17}=c_{17}+b_{17}$ so Option (D) is also incorrect

Hence, the correct answer is option (A).