Sets, Relations & Functions
Principle of Mathematical Induction
Grade 11
Question:
<p>Let \(P(n) = (3^{2^n} - 1)\). Then for \(n = 1\), \(P(1) = 3^2 - 1 = 9 - 1 = 8 = 2^3\), which is divisible by \(2^3\) but not by \(2^4\). Which of the following is the correct inductive conclusion?</p>
<p>(1) \(P(n)\) is divisible by \(2^{n+2}\) but not \(2^{n+3}\)</p>
<p>(2) \(P(n)\) is divisible by \(2^{n+1}\) but not \(2^{n+2}\)</p>
<p>(3) \(P(n)\) is divisible by \(2^{n+3}\) but not \(2^{n+4}\)</p>
<p>(4) \(P(n)\) is divisible by \(2^{n}\) but not \(2^{n+1}\)</p>
Step-by-Step Solution
Key Concept: Use mathematical induction with the telescoping property: P(n) = (3^(2^n) - 1) = (3^(2^(n-1)) - 1)(3^(2^(n-1)) + 1). Each factor contributes specific powers of 2, allowing us to track divisibility by powers of 2 across inductive steps.
<p><strong>Step 1:</strong> Use the factorization P(n) = 3^(2^n) - 1 = (3^(2^(n-1)))² - 1 = (3^(2^(n-1)) - 1)(3^(2^(n-1)) + 1)</p><p><strong>Step 2:</strong> By inductive hypothesis, P(n-1) = 3^(2^(n-1)) - 1 is divisible by 2^(n+2). This is the first factor.</p><p><strong>Step 3:</strong> For the second factor, note that 3 ≡ 3 (mod 8), so 3^(2^(n-1)) ≡ 1 (mod 8) for n ≥ 1 (by induction). Thus 3^(2^(n-1)) + 1 ≡ 2 (mod 4), meaning it's divisible by exactly 2¹, not higher powers.</p><p><strong>Step 4:</strong> Therefore P(n) = [divisible by 2^(n+2)] × [divisible by 2¹] is divisible by 2^(n+3) but not 2^(n+4).</p><p><strong>Correct Inductive Conclusion:</strong> P(n) is divisible by 2^(n+3) but not by 2^(n+4) for all n ≥ 1.</p><p>∴ Answer: A</p>
Correct Answer: A