Principles of Mathematical Induction: NCERT Ex 4.1 (Class 11 Maths)

Understanding the Principle of Mathematical Induction (PMI)

The Principle of Mathematical Induction (PMI) is a mathematical technique used to prove that a statement P(n) is true for every natural number n (i.e., for n = 1, 2, 3, ...). It's a fundamental concept in discrete mathematics and logic, allowing us to establish the truth of infinitely many cases with a finite number of steps. The power of PMI lies in its structure, which mirrors the intuitive idea of a chain reaction.

PMI is structured into two main steps:

1. Base Case (P(1) is true): This step involves showing that the statement P(n) holds true for the first natural number, typically n=1 (or sometimes n=0 or some other initial integer, depending on the problem). This is like proving that the first domino in a long line will fall. Without this initial push, nothing else can happen.

1. Inductive Step (P(k) is true implies P(k+1) is true): In this step, we assume that the statement P(n) is true for some arbitrary positive integer k (where P(k) is called the Inductive Hypothesis). Then, using this assumption, we prove that the statement P(n) must also be true for the next integer, k+1. This is the crucial 'domino effect' – proving that if any domino falls, it will definitely knock over the next one.

Once both these conditions are met, the Principle of Mathematical Induction guarantees that the statement P(n) is true for all natural numbers n. This method is widely used to prove identities, inequalities, and divisibility properties involving natural numbers.

Key Terms in Mathematical Induction

Principle of Mathematical Induction (PMI)

A proof technique used to prove that a statement P(n) holds for all natural numbers n. It consists of a base case and an inductive step.

Base Case

The first step of PMI, where we show the statement P(n) is true for the initial natural number, typically n=1.

Inductive Hypothesis

The assumption made in the inductive step that the statement P(n) is true for some arbitrary positive integer k (i.e., P(k) is true).

Inductive Step

The second step of PMI, where we prove that if the inductive hypothesis P(k) is true, then P(k+1) must also be true.

Worked Examples: Applying PMI from NCERT Ex 4.1

• Example 1: Prove that 1 + 3 + 3² + ... + 3ⁿ⁻¹ = (3ⁿ - 1) / 2 for all natural numbers n. Step 1: Base Case (P(1)) Let P(n) be the statement 1 + 3 + 3² + ... + 3ⁿ⁻¹ = (3ⁿ - 1) / 2. For n = 1, the Left Hand Side (LHS) is the first term: 3¹⁻¹ = 3⁰ = 1. The Right Hand Side (RHS) is (3¹ - 1) / 2 = (3 - 1) / 2 = 2 / 2 = 1. Since LHS = RHS, P(1) is true. Step 2: Inductive Hypothesis Assume that P(k) is true for some positive integer k. That is, 1 + 3 + 3² + ... + 3ᵏ⁻¹ = (3ᵏ - 1) / 2 Step 3: Inductive Step (Prove P(k+1)) We need to prove that P(k+1) is true, i.e., 1 + 3 + 3² + ... + 3ᵏ⁻¹ + 3⁽ᵏ⁺¹⁾⁻¹ = (3⁽ᵏ⁺¹⁾ - 1) / 2 Consider the LHS of P(k+1): 1 + 3 + 3² + ... + 3ᵏ⁻¹ + 3ᵏ Using the Inductive Hypothesis (from Step 2), we can replace the sum up to 3ᵏ⁻¹: = (3ᵏ - 1) / 2 + 3ᵏ To combine these terms, find a common denominator: = (3ᵏ - 1 + 2 3ᵏ) / 2 = (3ᵏ + 2 3ᵏ - 1) / 2 = (3 * 3ᵏ - 1) / 2 = (3ᵏ⁺¹ - 1) / 2 This is the RHS of P(k+1). Since P(1) is true, and P(k) implies P(k+1), by the Principle of Mathematical Induction, the statement P(n) is true for all natural numbers n.
• Example 2: Prove that n³ + 2n is a multiple of 3 for all natural numbers n. Step 1: Base Case (P(1)) Let P(n) be the statement "n³ + 2n is a multiple of 3". For n = 1, P(1) becomes 1³ + 2(1) = 1 + 2 = 3. Since 3 is a multiple of 3, P(1) is true. Step 2: Inductive Hypothesis Assume that P(k) is true for some positive integer k. That is, k³ + 2k is a multiple of 3. This means k³ + 2k = 3m for some integer m. Step 3: Inductive Step (Prove P(k+1)) We need to prove that P(k+1) is true, i.e., (k+1)³ + 2(k+1) is a multiple of 3. Consider (k+1)³ + 2(k+1): = (k³ + 3k² + 3k + 1) + (2k + 2) (Expanding (k+1)³ and 2(k+1)) = k³ + 3k² + 3k + 1 + 2k + 2 = (k³ + 2k) + 3k² + 3k + 3 From the Inductive Hypothesis (Step 2), we know that (k³ + 2k) = 3m. So, substitute 3m into the expression: = 3m + 3k² + 3k + 3 Factor out 3: = 3(m + k² + k + 1) Since (m + k² + k + 1) is an integer, (k+1)³ + 2(k+1) is a multiple of 3. Since P(1) is true, and P(k) implies P(k+1), by the Principle of Mathematical Induction, the statement P(n) is true for all natural numbers n.

Exam Tips for Principles of Mathematical Induction

Mastering PMI for exams requires attention to detail and structured presentation. Always clearly state your P(n) statement at the beginning. In the base case, explicitly show both the LHS and RHS and conclude that P(1) is true. For the inductive hypothesis, clearly write "Assume P(k) is true" and explicitly state what P(k) means. The inductive step is where most students make errors; ensure you use the inductive hypothesis correctly to transform the LHS of P(k+1) into its RHS. Avoid starting with P(k+1) and trying to work backwards; always start with one side and transform it using logical steps and the inductive hypothesis. Conclude your proof with a clear statement that by PMI, P(n) is true for all natural numbers.

Common Mistakes to Avoid

• Skipping the Base Case: Some students rush directly to the inductive step. Without proving P(1) (or the relevant initial case), the entire induction fails, like the first domino never falling.
• Incorrect Inductive Hypothesis: Not clearly stating or misunderstanding what P(k) represents can lead to errors in the inductive step. Remember, you assume P(k) is true, not P(k+1).
• Not Using the Inductive Hypothesis: A common error is to prove P(k+1) without ever utilizing the assumption that P(k) is true. The inductive hypothesis is the bridge that connects k to k+1.
• Algebraic Errors: Many mistakes stem from basic algebraic miscalculations when expanding or simplifying expressions in the inductive step. Practice careful manipulation of terms.
• Circular Reasoning: Trying to prove P(k+1) by implicitly assuming P(k+1) is true (or working backwards from the desired result) is a logical fallacy. Always proceed from P(k) to P(k+1).

Practice Questions with Solutions

• Q: Using the Principle of Mathematical Induction, prove that for every natural number n, 1 + 2 + 3 + ... + n = n(n+1)/2. A: Step 1: Base Case (P(1)) Let P(n) be the statement 1 + 2 + ... + n = n(n+1)/2. For n = 1, LHS = 1. RHS = 1(1+1)/2 = 1(2)/2 = 1. Since LHS = RHS, P(1) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some positive integer k. That is, 1 + 2 + ... + k = k(k+1)/2. Step 3: Inductive Step (Prove P(k+1)) We need to prove 1 + 2 + ... + k + (k+1) = (k+1)((k+1)+1)/2 = (k+1)(k+2)/2. Consider the LHS of P(k+1): 1 + 2 + ... + k + (k+1) Using the Inductive Hypothesis: = k(k+1)/2 + (k+1) = (k+1) [k/2 + 1] = (k+1) [(k+2)/2] = (k+1)(k+2)/2. This is the RHS of P(k+1). Final answer: By the Principle of Mathematical Induction, P(n) is true for all natural numbers n.
• Q: Prove by induction that 7ⁿ - 3ⁿ is divisible by 4 for all natural numbers n. A: Step 1: Base Case (P(1)) Let P(n) be the statement "7ⁿ - 3ⁿ is divisible by 4". For n = 1, 7¹ - 3¹ = 7 - 3 = 4. Since 4 is divisible by 4, P(1) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some positive integer k. That is, 7ᵏ - 3ᵏ is divisible by 4. So, 7ᵏ - 3ᵏ = 4m for some integer m. This implies 7ᵏ = 4m + 3ᵏ. Step 3: Inductive Step (Prove P(k+1)) We need to prove that 7ᵏ⁺¹ - 3ᵏ⁺¹ is divisible by 4. Consider 7ᵏ⁺¹ - 3ᵏ⁺¹: = 7 7ᵏ - 3ᵏ⁺¹ Substitute 7ᵏ = 4m + 3ᵏ from the Inductive Hypothesis: = 7 (4m + 3ᵏ) - 3ᵏ⁺¹ = 28m + 7 3ᵏ - 3 3ᵏ = 28m + (7 - 3) 3ᵏ = 28m + 4 3ᵏ = 4(7m + 3ᵏ) Since (7m + 3ᵏ) is an integer, 7ᵏ⁺¹ - 3ᵏ⁺¹ is divisible by 4. Final answer: By the Principle of Mathematical Induction, P(n) is true for all natural numbers n.
• Q: Prove by the Principle of Mathematical Induction that n < 2ⁿ for all natural numbers n. A: Step 1: Base Case (P(1)) Let P(n) be the statement "n < 2ⁿ". For n = 1, LHS = 1. RHS = 2¹ = 2. Since 1 < 2, P(1) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some positive integer k. That is, k < 2ᵏ. Step 3: Inductive Step (Prove P(k+1)) We need to prove (k+1) < 2ᵏ⁺¹. From the Inductive Hypothesis, we know k < 2ᵏ. Multiply both sides by 2: 2k < 2 * 2ᵏ 2k < 2ᵏ⁺¹ We want to show k+1 < 2ᵏ⁺¹. We know 2k = k + k. Since k is a natural number, k ≥ 1. Therefore, k+1 ≤ 2k. So, k+1 ≤ 2k < 2ᵏ⁺¹. Thus, k+1 < 2ᵏ⁺¹. Final answer: By the Principle of Mathematical Induction, P(n) is true for all natural numbers n.
• Q: Prove that 1² + 2² + ... + n² = n(n+1)(2n+1)/6 for all natural numbers n. A: Step 1: Base Case (P(1)) Let P(n) be the statement 1² + 2² + ... + n² = n(n+1)(2n+1)/6. For n = 1, LHS = 1² = 1. RHS = 1(1+1)(21+1)/6 = 1(2)(3)/6 = 6/6 = 1. Since LHS = RHS, P(1) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some positive integer k. That is, 1² + 2² + ... + k² = k(k+1)(2k+1)/6. Step 3: Inductive Step (Prove P(k+1)) We need to prove 1² + 2² + ... + k² + (k+1)² = (k+1)((k+1)+1)(2(k+1)+1)/6 = (k+1)(k+2)(2k+3)/6. Consider the LHS of P(k+1): 1² + 2² + ... + k² + (k+1)² Using the Inductive Hypothesis: = k(k+1)(2k+1)/6 + (k+1)² Factor out (k+1): = (k+1) [k(2k+1)/6 + (k+1)] = (k+1) [ (2k²+k + 6k+6) / 6 ] = (k+1) [ (2k²+7k+6) / 6 ] Factor the quadratic 2k²+7k+6. We look for two numbers that multiply to 12 (26) and add to 7 (3 and 4). 2k²+7k+6 = 2k²+3k+4k+6 = k(2k+3)+2(2k+3) = (k+2)(2k+3). So, the expression becomes: = (k+1) [(k+2)(2k+3) / 6] = (k+1)(k+2)(2k+3)/6. This is the RHS of P(k+1). Final answer: By the Principle of Mathematical Induction, P(n) is true for all natural numbers n.

Frequently Asked Questions