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_17 = a_16 + a_15, c_17 e c_16 + c_15, b_17 e b_16 + c_16

Permutations and Combinations PYQ — JEE Advanced 2012 · Shift 2 · Q35 with Solution

View written solutionFree

Correct answer: A, B, C

Understand the definitions

We form $n$ -digit positive integers using only digits $0$ and $1$ , with the condition that no two consecutive digits are $0$ .

Since the number is an $n$ -digit positive integer, the first digit cannot be $0$ . Hence the first digit must be $1$ .

Let:

$a_n$ = total number of such valid $n$ -digit numbers,
$b_n$ = number of such valid $n$ -digit numbers ending in $1$ ,
$c_n$ = number of such valid $n$ -digit numbers ending in $0$ .

Clearly, $a_n=b_n+c_n.$

Find recurrences for $b_n$ and $c_n$

For $b_n$

A valid $n$ -digit number ending in $1$ can be formed by appending $1$ to any valid $(n-1)$ -digit number.

So, $b_n=a_{n-1}=b_{n-1}+c_{n-1}.$

For $c_n$

A valid $n$ -digit number ending in $0$ cannot have the previous digit as $0$ . So the $(n-1)$ -th digit must be $1$ .

Hence, a valid $n$ -digit number ending in $0$ is obtained by appending $0$ to a valid $(n-1)$ -digit number ending in $1$ . Thus, $c_n=b_{n-1}.$

Find recurrence for $a_n$

Using $a_n=b_n+c_n,$ we get $a_n=a_{n-1}+b_{n-1}.$ But since $b_{n-1}=a_{n-2},$ we obtain $a_n=a_{n-1}+a_{n-2}.$

Therefore, $a_{17}=a_{16}+a_{15}.$ So Option A is correct.

Check the other options

Option B: $c_{17}=c_{16}+c_{15}$

We know $c_n=b_{n-1}.$ So $c_{17}=b_{16},$ not generally $c_{16}+c_{15}$ .

Also, using $c_n=b_{n-1}=a_{n-2}$ ,

c_{16}=a_{14},\ c_{15}=a_{13}.$$ Then Option B would say $$a_{15}=a_{14}+a_{13},$$ which is true by Fibonacci recurrence. Hence **B is also true**. --- ### Option C: $b_{17}=b_{16}+c_{16}$ Since $$a_{16}=b_{16}+c_{16}$$ and also $$b_{17}=a_{16},$$ we get $$b_{17}=b_{16}+c_{16}.$$ So **C is true**. --- ### Option D: $a_{17}=c_{17}+b_{16}$ Now, $$c_{17}=b_{16}.$$ So the RHS becomes $$c_{17}+b_{16}=2b_{16}.$$ But $$a_{17}=b_{17}+c_{17}=a_{16}+b_{16},$$ which is not generally equal to $2b_{16}$. Using $b_{16}=a_{15}$ and $c_{17}=a_{15}$, RHS $=2a_{15}$, while $$a_{17}=a_{16}+a_{15},$$ not equal in general. So **D is false**. --- 5. **Conclusion** The correct statements are: - **A is true** - **B is true** - **C is true** - **D is false** So this is actually a **multiple-correct** situation, not a single-correct MCQ. The stored answer says only **A**, but **B and C** are also correct.

More from Permutations and Combinations

View written solutionFree

Correct answer: A, B, C

Understand the definitions

We form $n$ -digit positive integers using only digits $0$ and $1$ , with the condition that no two consecutive digits are $0$ .

Since the number is an $n$ -digit positive integer, the first digit cannot be $0$ . Hence the first digit must be $1$ .

Let:

$a_n$ = total number of such valid $n$ -digit numbers,
$b_n$ = number of such valid $n$ -digit numbers ending in $1$ ,
$c_n$ = number of such valid $n$ -digit numbers ending in $0$ .

Clearly, $a_n=b_n+c_n.$

Find recurrences for $b_n$ and $c_n$

For $b_n$

A valid $n$ -digit number ending in $1$ can be formed by appending $1$ to any valid $(n-1)$ -digit number.

So, $b_n=a_{n-1}=b_{n-1}+c_{n-1}.$

For $c_n$

A valid $n$ -digit number ending in $0$ cannot have the previous digit as $0$ . So the $(n-1)$ -th digit must be $1$ .

Hence, a valid $n$ -digit number ending in $0$ is obtained by appending $0$ to a valid $(n-1)$ -digit number ending in $1$ . Thus, $c_n=b_{n-1}.$

Find recurrence for $a_n$

Using $a_n=b_n+c_n,$ we get $a_n=a_{n-1}+b_{n-1}.$ But since $b_{n-1}=a_{n-2},$ we obtain $a_n=a_{n-1}+a_{n-2}.$

Therefore, $a_{17}=a_{16}+a_{15}.$ So Option A is correct.

Check the other options

Option B: $c_{17}=c_{16}+c_{15}$

We know $c_n=b_{n-1}.$ So $c_{17}=b_{16},$ not generally $c_{16}+c_{15}$ .

Also, using $c_n=b_{n-1}=a_{n-2}$ ,

c_{16}=a_{14},\ c_{15}=a_{13}.$$ Then Option B would say $$a_{15}=a_{14}+a_{13},$$ which is true by Fibonacci recurrence. Hence **B is also true**. --- ### Option C: $b_{17}=b_{16}+c_{16}$ Since $$a_{16}=b_{16}+c_{16}$$ and also $$b_{17}=a_{16},$$ we get $$b_{17}=b_{16}+c_{16}.$$ So **C is true**. --- ### Option D: $a_{17}=c_{17}+b_{16}$ Now, $$c_{17}=b_{16}.$$ So the RHS becomes $$c_{17}+b_{16}=2b_{16}.$$ But $$a_{17}=b_{17}+c_{17}=a_{16}+b_{16},$$ which is not generally equal to $2b_{16}$. Using $b_{16}=a_{15}$ and $c_{17}=a_{15}$, RHS $=2a_{15}$, while $$a_{17}=a_{16}+a_{15},$$ not equal in general. So **D is false**. --- 5. **Conclusion** The correct statements are: - **A is true** - **B is true** - **C is true** - **D is false** So this is actually a **multiple-correct** situation, not a single-correct MCQ. The stored answer says only **A**, but **B and C** are also correct.

Permutations and Combinations question

Permutations and Combinations question

For $b_n$

For $c_n$

Option B: $c_{17}=c_{16}+c_{15}$

More from Permutations and Combinations

Permutations and Combinations question

Permutations and Combinations question

For $b_n$

For $c_n$

Option B: $c_{17}=c_{16}+c_{15}$

More from Permutations and Combinations

For bnb_nbn​

For cnc_ncn​

Option B: c17=c16+c15c_{17}=c_{16}+c_{15}c17​=c16​+c15​

More from Permutations and Combinations

For bnb_nbn​

For cnc_ncn​

Option B: c17=c16+c15c_{17}=c_{16}+c_{15}c17​=c16​+c15​

More from Permutations and Combinations

For $b_n$

For $c_n$

Option B: $c_{17}=c_{16}+c_{15}$

For $b_n$

For $c_n$

Option B: $c_{17}=c_{16}+c_{15}$