Principles of Mathematical Induction (PMI) - Class 11 Maths NCERT

What is the Principle of Mathematical Induction (PMI)?

The Principle of Mathematical Induction (PMI) is a fundamental and elegant proof technique used to establish the truth of a mathematical statement or formula for all natural numbers (1, 2, 3, ...). Imagine you have an infinitely long line of dominoes. If you want to be sure that all the dominoes will fall, you don't need to push each one individually. You just need to do two things:

1. Push the first domino: Make sure the first domino falls.
2. Ensure a chain reaction: Show that if any one domino falls, it will definitely knock down the next one in the line.

If these two conditions are met, you can logically conclude that all the dominoes will eventually fall. This is precisely the essence of the Principle of Mathematical Induction. It allows us to prove statements P(n) for all n ∈ N (natural numbers) by verifying just two conditions, which we will explore in detail.

The Three Essential Steps of Mathematical Induction

1. Step 1: The Base Case (P(1)) — The first step is to verify that the statement P(n) is true for the initial value of n, which is typically n=1 (or sometimes n=0 or n=k_0 for some integer k_0). This is crucial because it 'starts' the chain reaction. Without a base case, there's nothing to initiate the induction. To do this, simply substitute n=1 into the given statement P(n) and show that both sides of the equation or inequality are equal or hold true.
2. Step 2: The Inductive Hypothesis (P(k)) — In this step, we assume that the statement P(n) is true for some arbitrary positive integer k, where k ≥ 1 (or k ≥ k_0 as per the base case). This assumption, denoted as P(k) is true, is called the Inductive Hypothesis. It's the 'if a domino falls' part of our analogy. We are not proving P(k) here; we are simply assuming its truth to help us prove the next step. Write down the statement P(k) clearly based on P(n).
3. Step 3: The Inductive Step (P(k+1)) — This is the core of the proof. Using the Inductive Hypothesis (that P(k) is true), we must prove that the statement P(n) is also true for the next integer, n = k+1. This is denoted as P(k+1). This step demonstrates the 'chain reaction' – if P(k) is true, then P(k+1) logically follows. To do this, substitute n=k+1 into P(n) to get P(k+1), then manipulate one side of P(k+1) (usually the LHS) using the assumption P(k) to show it equals the other side (RHS of P(k+1)). If you successfully prove P(k+1) using P(k), then by the Principle of Mathematical Induction, the statement P(n) is true for all natural numbers n.

Worked Examples on Mathematical Induction

• Example 1: Prove that for all natural numbers n, 1 + 2 + 3 + ... + n = n(n+1)/2. Solution: Let P(n) be the statement 1 + 2 + 3 + ... + n = n(n+1)/2. Step 1: Base Case (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 that P(k) is true for some positive integer k. That is, assume: 1 + 2 + 3 + ... + k = k(k+1)/2 Step 3: Inductive Step (Prove P(k+1)) We need to prove that P(k+1) is true, i.e., 1 + 2 + 3 + ... + k + (k+1) = (k+1)((k+1)+1)/2 = (k+1)(k+2)/2. Consider the LHS of P(k+1): LHS = (1 + 2 + 3 + ... + k) + (k+1) Using the Inductive Hypothesis (from Step 2), we can substitute k(k+1)/2 for the sum (1 + 2 + ... + k): LHS = k(k+1)/2 + (k+1) Take (k+1) common: LHS = (k+1) [k/2 + 1] LHS = (k+1) [(k+2)/2] LHS = (k+1)(k+2)/2 This is equal to the RHS of P(k+1). Thus, P(k+1) is true whenever P(k) is true. Conclusion: By the Principle of Mathematical Induction, the statement P(n) is true for all natural numbers n.
• Example 2: Prove that n^3 + 2n is divisible by 3 for all natural numbers n. Solution: Let P(n) be the statement "n^3 + 2n is divisible by 3". Step 1: Base Case (n=1) For n=1, P(1) is 1^3 + 2(1) = 1 + 2 = 3. Since 3 is divisible by 3, P(1) is true. Step 2: Inductive Hypothesis Assume that P(k) is true for some positive integer k. That is, assume k^3 + 2k is divisible by 3. This means k^3 + 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)^3 + 2(k+1) is divisible by 3. Consider the expression for P(k+1): (k+1)^3 + 2(k+1) Expand (k+1)^3: = (k^3 + 3k^2 + 3k + 1) + (2k + 2) Rearrange terms to group k^3 + 2k: = (k^3 + 2k) + 3k^2 + 3k + 3 From the Inductive Hypothesis (Step 2), we know k^3 + 2k = 3m. = 3m + 3k^2 + 3k + 3 Factor out 3: = 3(m + k^2 + k + 1) Since (m + k^2 + k + 1) is an integer, 3(m + k^2 + k + 1) is divisible by 3. Thus, P(k+1) is true whenever P(k) is true. Conclusion: By the Principle of Mathematical Induction, n^3 + 2n is divisible by 3 for all natural numbers n.

Common Mistakes and Important Exam Tips

To excel in PMI problems, be aware of these common pitfalls and follow these tips:

1. Missing or Incorrect Base Case: Always clearly state and verify the base case. A proof without a valid base case is incomplete and incorrect. If the problem specifies n ≥ 2, then P(2) is your base case, not P(1).
2. Assuming P(k+1) instead of Proving it: The most common mistake! You assume P(k) is true, and then use this assumption to prove P(k+1). You cannot start by assuming P(k+1) is true.
3. Algebraic Errors in the Inductive Step: The inductive step often involves careful algebraic manipulation. Double-check your expansions, factorisations, and substitutions. These are where most calculation errors occur.
4. Not Clearly Stating Hypotheses: Explicitly write "Assume P(k) is true" for the inductive hypothesis and "We need to prove P(k+1) is true" for the inductive step. This structure helps you stay organised and shows the examiner your understanding.
5. Misapplying PMI: PMI is specifically for statements about natural numbers. Don't try to apply it to real numbers or other sets where it doesn't fit.
6. Writing the Conclusion: Always conclude your proof with a clear statement that, by the Principle of Mathematical Induction, the given statement is true for all natural numbers n.

Practice Questions with Solutions

• Q: Prove by the Principle of Mathematical Induction that 1 + 3 + 5 + ... + (2n-1) = n^2 for all natural numbers n. A: Step 1: Base Case (n=1) LHS = 2(1)-1 = 1 RHS = 1^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 + 3 + 5 + ... + (2k-1) = k^2. Step 3: Inductive Step (Prove P(k+1)) We need to prove P(k+1), i.e., 1 + 3 + 5 + ... + (2(k+1)-1) = (k+1)^2. LHS = (1 + 3 + 5 + ... + (2k-1)) + (2(k+1)-1) Using the Inductive Hypothesis: LHS = k^2 + (2k + 2 - 1) LHS = k^2 + 2k + 1 LHS = (k+1)^2 This is equal to the RHS of P(k+1). Final answer: By PMI, 1 + 3 + 5 + ... + (2n-1) = n^2 is true for all natural numbers n.
• Q: Prove by PMI that 1/(12) + 1/(23) + 1/(34) + ... + 1/(n(n+1)) = n/(n+1) for all natural numbers n. A: Step 1: Base Case (n=1) LHS = 1/(12) = 1/2 RHS = 1/(1+1) = 1/2 Since LHS = RHS, P(1) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some positive integer k. That is, 1/(12) + ... + 1/(k(k+1)) = k/(k+1). Step 3: Inductive Step (Prove P(k+1)) We need to prove P(k+1), i.e., 1/(12) + ... + 1/((k+1)((k+1)+1)) = (k+1)/((k+1)+1). LHS = [1/(12) + ... + 1/(k(k+1))] + 1/((k+1)(k+2)) Using the Inductive Hypothesis: LHS = k/(k+1) + 1/((k+1)(k+2)) Find a common denominator (k+1)(k+2): LHS = [k(k+2) + 1] / ((k+1)(k+2)) LHS = (k^2 + 2k + 1) / ((k+1)(k+2)) LHS = (k+1)^2 / ((k+1)(k+2)) Cancel out one (k+1) term: LHS = (k+1) / (k+2) This is equal to the RHS of P(k+1). Final answer: By PMI, 1/(12) + ... + 1/(n(n+1)) = n/(n+1) is true for all natural numbers n.
• Q: Prove by PMI that 4^n + 15n - 1 is divisible by 9 for all natural numbers n. A: Step 1: Base Case (n=1) For n=1, P(1) is 4^1 + 15(1) - 1 = 4 + 15 - 1 = 18. Since 18 is divisible by 9, P(1) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some positive integer k. That is, 4^k + 15k - 1 is divisible by 9. So, 4^k + 15k - 1 = 9m for some integer m. This implies 4^k = 9m - 15k + 1. Step 3: Inductive Step (Prove P(k+1)) We need to prove P(k+1), i.e., 4^(k+1) + 15(k+1) - 1 is divisible by 9. Consider the expression for P(k+1): 4^(k+1) + 15(k+1) - 1 = 4 4^k + 15k + 15 - 1 = 4 4^k + 15k + 14 Substitute 4^k = 9m - 15k + 1 from the Inductive Hypothesis: = 4(9m - 15k + 1) + 15k + 14 = 36m - 60k + 4 + 15k + 14 = 36m - 45k + 18 Factor out 9: = 9(4m - 5k + 2) Since (4m - 5k + 2) is an integer, 9(4m - 5k + 2) is divisible by 9. Final answer: By PMI, 4^n + 15n - 1 is divisible by 9 for all natural numbers n.
• Q: Prove by PMI that (1+x)^n ≥ 1+nx for all natural numbers n and x > -1. A: Step 1: Base Case (n=1) LHS = (1+x)^1 = 1+x RHS = 1+1x = 1+x Since LHS = RHS, P(1) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some positive integer k. That is, (1+x)^k ≥ 1+kx. Step 3: Inductive Step (Prove P(k+1)) We need to prove P(k+1), i.e., (1+x)^(k+1) ≥ 1+(k+1)x. Consider the LHS of P(k+1): LHS = (1+x)^(k+1) = (1+x)^k (1+x) From the Inductive Hypothesis, we know (1+x)^k ≥ 1+kx. Also, since x > -1, (1+x) > 0. Multiplying an inequality by a positive number preserves the inequality direction: LHS ≥ (1+kx)(1+x) Expand the RHS: LHS ≥ 1 + x + kx + kx^2 LHS ≥ 1 + (k+1)x + kx^2 Since k is a natural number and x^2 ≥ 0, kx^2 ≥ 0. Therefore, 1 + (k+1)x + kx^2 ≥ 1 + (k+1)x. So, (1+x)^(k+1) ≥ 1 + (k+1)x. Final answer: By PMI, (1+x)^n ≥ 1+nx is true for all natural numbers n and x > -1.

Frequently Asked Questions