Let `a_(n)` denote the number of all n-digit numbers formed by the digits 0,1 or both such that no consecutive digits in them are 0. Let `b_(n)` be the number of such n-digit integers ending with digit 1 and let `c_(n)` be the number of such n-digit integers ending with digit 0. Which of the following is correct ?

Options

A. 7
B. 8
C. 9
D. 11

Explanation

To solve the problem, we need to derive the relationships between \( a_n \), \( b_n \), and \( c_n \) based on the conditions provided.

### Step 1: Define the variables
- Let \( a_n \) be the total number of n-digit numbers formed by the digits 0 and 1, such that no two consecutive digits are 0.
- Let \( b_n \) be the number of such n-digit integers ending with the digit 1.
- Let \( c_n \) be the number of such n-digit integers ending with the digit 0.

### Step 2: Establish the relationship
Since any n-digit number can either end with 0 or 1, we can express \( a_n \) as:
\[ a_n = b_n + c_n \]

### Step 3: Analyze \( b_n \) and \( c_n \)
1. **For \( b_n \)**: If an n-digit number ends with 1, the previous digit can be either 0 or 1. Therefore, the first \( n-1 \) digits can be any valid configuration of \( n-1 \) digits, which is \( a_{n-1} \). Thus:
\[ b_n = a_{n-1} \]

2. **For \( c_n \)**: If an n-digit number ends with 0, the digit before it must be 1 (to avoid consecutive 0s). Therefore, the first \( n-2 \) digits can be any valid configuration of \( n-2 \) digits, which is \( a_{n-2} \). Thus:
\[ c_n = b_{n-1} \]

### Step 4: Substitute \( b_n \) into \( c_n \)
From the previous step, we have:
\[ c_n = b_{n-1} = a_{n-2} \]

### Step 5: Substitute \( b_n \) and \( c_n \) into the equation for \( a_n \)
Now substituting \( b_n \) and \( c_n \) into the equation for \( a_n \):
\[ a_n = b_n + c_n = a_{n-1} + a_{n-2} \]

### Step 6: Base cases
We need to establish base cases to solve the recurrence relation:
- For \( n = 1 \): The valid 1-digit numbers are {1}. Thus, \( a_1 = 1 \).
- For \( n = 2 \): The valid 2-digit numbers are {10, 11}. Thus, \( a_2 = 2 \).

### Step 7: Calculate further values
Using the recurrence relation \( a_n = a_{n-1} + a_{n-2} \):
- For \( n = 3 \):
\[ a_3 = a_2 + a_1 = 2 + 1 = 3 \]
- For \( n = 4 \):
\[ a_4 = a_3 + a_2 = 3 + 2 = 5 \]
- For \( n = 5 \):
\[ a_5 = a_4 + a_3 = 5 + 3 = 8 \]
- For \( n = 6 \):
\[ a_6 = a_5 + a_4 = 8 + 5 = 13 \]

### Final Result
The relationship established is:
\[ a_n = a_{n-1} + a_{n-2} \]
with base cases \( a_1 = 1 \) and \( a_2 = 2 \).