Principle of Mathematical Induction: Class 11 Maths NCERT

Understanding the Principle of Mathematical Induction

The Principle of Mathematical Induction (PMI) is a method used to prove that a given statement P(n) is true for all natural numbers n (or for all natural numbers greater than or equal to some initial natural number). It's a cornerstone of discrete mathematics and forms the basis for many proofs in algebra, number theory, and computer science. The core idea is to establish a chain of truth.

Imagine you have an infinitely long ladder. To prove you can climb to any rung, you only need to show two things: first, that you can reach the very first rung (the starting point), and second, that if you can reach any given rung, you can always reach the next rung. If both these conditions are met, then logically, you can reach every single rung on the ladder. This is the essence of PMI. It allows us to prove an infinite number of cases by checking just two conditions, making it incredibly efficient and powerful. This technique is especially useful when dealing with sequences, series, divisibility properties, and inequalities involving natural numbers.

Key Terms in Mathematical Induction

Proposition P(n)

This is the statement or property that you want to prove is true for all natural numbers 'n'. For example, P(n) could be "1 + 2 + ... + n = n(n+1)/2" or "n^3 + 2n is divisible by 3".

Base Case (P(n₀))

This is the first step where you prove the proposition P(n) for the initial natural number, usually n=1. Sometimes, the problem might specify a different starting point, like n=0 or n=2, depending on the context of the statement.

Inductive Hypothesis (P(k))

In this step, you assume that the proposition P(n) is true for some arbitrary positive integer 'k' (where k ≥ n₀). This assumption is crucial and acts as the 'given' information you will use in the next step.

Inductive Step (P(k+1))

This is the most critical part. Here, you use the Inductive Hypothesis (that P(k) is true) to prove that P(k+1) is also true. If you can successfully demonstrate this implication, you've completed the proof by induction.

The Three Essential Steps of PMI

1. Step 1: The Base Case (P(1) or P(n₀)) — The first step is to verify that the statement P(n) is true for the initial value of n. This is usually n=1 for statements about all natural numbers. Substitute n=1 (or the given initial value n₀) into the statement P(n) and show that both sides of the equation (or the condition) hold true. This establishes the starting point for your inductive argument.
2. Step 2: The Inductive Hypothesis (Assume P(k)) — Assume that the statement P(n) is true for some arbitrary positive integer k, where k is greater than or equal to the base case value (k ≥ n₀). This assumption is called the Inductive Hypothesis. You are not proving P(k) here; you are simply stating that if P(k) is true, then you will proceed to the next step to prove P(k+1).
3. Step 3: The Inductive Step (Prove P(k+1)) — Using your Inductive Hypothesis (the assumption that P(k) is true), you must now prove that the statement P(n) is also true for n = k+1. This is where you demonstrate the 'chain reaction'. You typically start with one side of P(k+1) and, through algebraic manipulation, substitute the expression from P(k) to transform it into the other side of P(k+1). If you successfully show that P(k) implies P(k+1), then by the Principle of Mathematical Induction, the statement P(n) is true for all natural numbers n (or n ≥ n₀).

Fully Worked Examples

• Example 1: Proving a Summation Formula Prove by the Principle of Mathematical Induction that for all natural numbers n, the sum of the first n natural numbers is given by the formula: 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) For n = 1, the left-hand side (LHS) = 1. The right-hand side (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 arbitrary positive integer k. That is, assume: 1 + 2 + 3 + ... + k = k(k+1)/2 --- (Equation 1) Step 3: Inductive Step (Prove P(k+1)) We need to prove that P(k+1) is true, i.e., we need to show: 1 + 2 + 3 + ... + k + (k+1) = (k+1)((k+1)+1)/2 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2 Let's start with the LHS of P(k+1): LHS = (1 + 2 + 3 + ... + k) + (k+1) From our Inductive Hypothesis (Equation 1), we know that (1 + 2 + 3 + ... + k) can be replaced by k(k+1)/2. So, LHS = k(k+1)/2 + (k+1) Now, take (k+1) as a common factor: 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). Since P(k+1) is true whenever P(k) is true, by the Principle of Mathematical Induction, the statement P(n) is true for all natural numbers n. Example 2: Proving Divisibility Prove by the Principle of Mathematical Induction that for every natural number n, 7^n - 3^n is divisible by 4. Solution: Let P(n) be the statement: 7^n - 3^n is divisible by 4. Step 1: Base Case (n=1) For n = 1, P(1) is 7^1 - 3^1 = 7 - 3 = 4. Since 4 is divisible by 4, P(1) is true. Step 2: Inductive Hypothesis Assume that P(k) is true for some arbitrary positive integer k. That is, assume: 7^k - 3^k is divisible by 4. This means 7^k - 3^k = 4m, for some integer m. --- (Equation 1) From this, we can write 7^k = 4m + 3^k. Step 3: Inductive Step (Prove P(k+1)) We need to prove that P(k+1) is true, i.e., 7^(k+1) - 3^(k+1) is divisible by 4. Consider the expression for P(k+1): 7^(k+1) - 3^(k+1) = 7^k 7^1 - 3^(k+1) Substitute 7^k = 4m + 3^k from Equation 1: = (4m + 3^k) 7 - 3^(k+1) = 28m + 7 3^k - 3^(k+1) = 28m + 7 3^k - 3^k * 3^1 = 28m + 3^k (7 - 3) = 28m + 3^k (4) = 4 (7m + 3^k) Since (7m + 3^k) is an integer, the expression 4(7m + 3^k) is clearly divisible by 4. Therefore, 7^(k+1) - 3^(k+1) is divisible by 4. Since P(k+1) is true whenever P(k) is true, by the Principle of Mathematical Induction, the statement P(n) is true for all natural numbers n.

Exam Tips for Principle of Mathematical Induction

Mastering PMI for exams requires attention to detail and clear presentation. Here are some crucial tips:

• Clearly State P(n): Always begin by clearly defining the statement P(n) that you intend to prove. This sets the stage for your entire proof.
• Don't Skip Any Step: Each of the three steps (Base Case, Inductive Hypothesis, Inductive Step) is indispensable. Omitting any step, or performing it incorrectly, will result in loss of marks. Even if a step seems trivial, write it down explicitly.
• Show How P(k) Implies P(k+1): The core of the inductive step is showing the logical connection. Do not just prove P(k+1) independently. You must use the assumption that P(k) is true to derive P(k+1). This usually involves substituting the expression from P(k) into the P(k+1) expression.
• Algebraic Accuracy: Most errors in the inductive step stem from algebraic mistakes. Be meticulous with your calculations, factorisation, and simplification. Double-check your steps.
• Understand the Starting Value (n₀): While often n₀=1, sometimes problems specify n₀ > 1 (e.g., prove for n ≥ 5). Ensure your base case matches the specified starting value. This is a common trap.
• Conclusion: Always conclude your proof with a formal statement, "By the Principle of Mathematical Induction, P(n) is true for all natural numbers n," or similar phrasing, explicitly mentioning PMI.

Practice Questions with Solutions

• Q: Prove by the Principle of Mathematical Induction that for every natural number n, the sum of the first n odd numbers is n^2. 1 + 3 + 5 + ... + (2n-1) = n^2. A: Step 1: Base Case (n=1) For n=1, LHS = 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): 1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)^2. Consider LHS of P(k+1): LHS = [1 + 3 + 5 + ... + (2k-1)] + (2k+2-1) LHS = k^2 + (2k+1) (Using Inductive Hypothesis) LHS = (k+1)^2 This is the RHS of P(k+1). Thus, P(k+1) is true whenever P(k) is true. 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 for every natural number n, 3^(2n+2) - 8n - 9 is divisible by 64. A: Step 1: Base Case (n=1) For n=1, P(1) is 3^(2(1)+2) - 8(1) - 9 = 3^4 - 8 - 9 = 81 - 17 = 64. Since 64 is divisible by 64, P(1) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some positive integer k. That is, 3^(2k+2) - 8k - 9 is divisible by 64. So, 3^(2k+2) - 8k - 9 = 64m for some integer m. This implies 3^(2k+2) = 64m + 8k + 9. Step 3: Inductive Step (Prove P(k+1)) We need to prove P(k+1): 3^(2(k+1)+2) - 8(k+1) - 9 is divisible by 64. Consider the expression for P(k+1): 3^(2k+4) - 8k - 8 - 9 = 3^(2k+2) 3^2 - 8k - 17 Substitute 3^(2k+2) = 64m + 8k + 9: = (64m + 8k + 9) 9 - 8k - 17 = 576m + 72k + 81 - 8k - 17 = 576m + 64k + 64 = 64(9m + k + 1) Since (9m + k + 1) is an integer, the expression is divisible by 64. 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 for every natural number n ≥ 4, 2^n < n! (where n! denotes n factorial). A: Step 1: Base Case (n=4) For n=4, LHS = 2^4 = 16. RHS = 4! = 4321 = 24. Since 16 < 24, P(4) is true. Step 2: Inductive Hypothesis Assume P(k) is true for some integer k ≥ 4. That is, 2^k < k!. Step 3: Inductive Step (Prove P(k+1)) We need to prove P(k+1): 2^(k+1) < (k+1)!. Consider LHS of P(k+1): LHS = 2^(k+1) = 2^k 2 From Inductive Hypothesis, we know 2^k < k!. So, 2^k 2 < k! 2 --- (Equation 1) We also know that for k ≥ 4, 2 < k+1. Multiply both sides of Equation 1 by (k+1)/2 (which is > 1 for k >=4): 2^k 2 < k! (k+1) (since 2 < k+1 for k >= 4) 2^(k+1) < (k+1)! Thus, P(k+1) is true whenever P(k) is true. Final answer: By the Principle of Mathematical Induction, P(n) is true for all natural numbers n ≥ 4.
• Q: Prove by the Principle of Mathematical Induction that for all natural numbers n, 1^3 + 2^3 + 3^3 + ... + n^3 = [n(n+1)/2]^2. A: Step 1: Base Case (n=1) For n=1, LHS = 1^3 = 1. RHS = [1(1+1)/2]^2 = [1(2)/2]^2 = 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 + 2^3 + ... + k^3 = [k(k+1)/2]^2. Step 3: Inductive Step (Prove P(k+1)) We need to prove P(k+1): 1^3 + 2^3 + ... + k^3 + (k+1)^3 = [(k+1)((k+1)+1)/2]^2 = [(k+1)(k+2)/2]^2. Consider LHS of P(k+1): LHS = (1^3 + 2^3 + ... + k^3) + (k+1)^3 Using Inductive Hypothesis: LHS = [k(k+1)/2]^2 + (k+1)^3 LHS = k^2(k+1)^2/4 + (k+1)^3 Take (k+1)^2 as a common factor: LHS = (k+1)^2 [k^2/4 + (k+1)] LHS = (k+1)^2 [(k^2 + 4k + 4)/4] LHS = (k+1)^2 [(k+2)^2/4] LHS = [(k+1)(k+2)/2]^2 This is the RHS of P(k+1). Thus, P(k+1) is true whenever P(k) is true. Final answer: By the Principle of Mathematical Induction, P(n) is true for all natural numbers n.

Frequently Asked Questions