Permutations & Combinations
Digit arrangements with constraints
Grade None
Question:
<p>Let <i>n</i> denote the number of all <i>n</i>-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 <i>n</i>-digit integers ending with digit 1 and \(c_n\) = the number of such <i>n</i>-digit integers ending with digit 0.<br><br><b>Problem 2:</b> Which of the following is correct?</p>
<p>\(a_{17} = a_{16} + a_{15}\)</p>
<p>\(c_{17} \neq c_{16} + c_{15}\)</p>
<p>\(b_{17} \neq b_{16} + c_{16}\)</p>
<p>\(a_{17} = c_{17} + b_{16}\)</p>
Step-by-Step Solution
Key Concept: Set up recurrence relations by analyzing how valid n-digit numbers can be formed from valid (n-1)-digit numbers: numbers ending in 1 can be followed by either 0 or 1, while numbers ending in 0 can only be followed by 1 (to avoid consecutive 0s).
<p><strong>Step 1:</strong> Establish the recurrence by considering what digit can follow each ending.</p><p>If an (n-1)-digit valid number ends in 1, we can append either 0 or 1: contributes to both b_n and c_n.</p><p>If an (n-1)-digit valid number ends in 0, we can only append 1: contributes only to b_n.</p><p><strong>Step 2:</strong> Write the recurrences:</p><p>• b_n = b_{n-1} + c_{n-1} (append 1 to numbers ending in 1 or 0)</p><p>• c_n = b_{n-1} (append 0 only to numbers ending in 1)</p><p><strong>Step 3:</strong> Find initial conditions with first digit ≠ 0:</p><p>• b_1 = 1 (just "1")</p><p>• c_1 = 0 (can't have "0" as 1-digit number)</p><p><strong>Step 4:</strong> Verify the relation a_n = b_n + c_n satisfies:</p><p>a_n = b_n + c_n = (b_{n-1} + c_{n-1}) + b_{n-1} = b_{n-1} + (b_{n-1} + c_{n-1}) = a_{n-1} + b_{n-1}</p><p>Also: b_n = b_{n-1} + c_{n-1} = a_{n-1}, so a_n = a_{n-1} + a_{n-2}</p><p>∴ The correct relation is typically: <strong>a_n = a_{n-1} + a_{n-2}</strong> (Fibonacci-like) with a_1 = 1, a_2 = 2</p>
Correct Answer: A