Class 11 Mathematics Notes Chapter 4 (Principle of mathematical induction) – Mathematics Book

Alright class, let's dive into a very important tool in mathematics: the Principle of Mathematical Induction (PMI). While it might seem abstract initially, it's a powerful technique for proving statements that hold true for all natural numbers. Think of it like setting up an infinite line of dominoes.

Chapter 4: Principle of Mathematical Induction

1. Introduction: What is Mathematical Induction?

• Mathematical Induction is a technique used to prove that a given mathematical statement (or proposition), denoted as P(n), is true for all natural numbers (n ∈ N), i.e., for n = 1, 2, 3, ...
• It's particularly useful for proving formulas related to sums of series, divisibility properties, inequalities, etc., that depend on a natural number 'n'.
• Analogy: Imagine an infinite line of dominoes. To ensure all dominoes fall:
  • You must push the first domino. (Base Case)
  • You must ensure that if any domino falls, it knocks over the next one. (Inductive Step)
  • If both conditions are met, you can conclude that all dominoes will fall.

2. The Principle of Mathematical Induction (Formal Statement):

Let P(n) be a given statement involving the natural number n. To prove that P(n) is true for all n ∈ N, we perform the following two steps:

• Step 1: Base Case (or Basis Step):

  • Verify that the statement P(n) is true for the initial value, usually n = 1.
  • We show that P(1) is true.
  • (Sometimes, the statement might be true for n ≥ a, where 'a' is some integer greater than 1. In that case, the base case is to prove P(a) is true).

• Step 2: Inductive Step:

  • Assume that the statement P(n) is true for some arbitrary positive integer 'k'. This assumption is called the Inductive Hypothesis. So, we assume P(k) is true.
  • Using this assumption (P(k) is true), prove that the statement P(n) is also true for the next integer, n = k + 1. That is, we need to prove P(k+1) is true.

• Conclusion: If both the Base Case (P(1) is true) and the Inductive Step (Assuming P(k) is true implies P(k+1) is true) are established, then by the Principle of Mathematical Induction, the statement P(n) is true for all natural numbers n.

3. Working Steps for Solving Problems using PMI:

Let the statement be P(n).

• Step I (Base Case): Show that P(1) is true. Substitute n=1 in the statement and verify its truth.
• Step II (Inductive Hypothesis): Assume that P(k) is true for some positive integer k. Write down the statement P(k) explicitly.
• Step III (Inductive Step): Aim to prove that P(k+1) is true. Write down the statement P(k+1). Use the assumption from Step II (P(k) is true) to manipulate the expression for P(k+1) and show that it holds true. This usually involves algebraic manipulation, often starting with one side of the P(k+1) statement and using P(k) to reach the other side.
• Step IV (Conclusion): Since P(1) is true and P(k) true ⇒ P(k+1) true, conclude by the Principle of Mathematical Induction that P(n) is true for all n ∈ N.

4. Example:

Prove that for all n ∈ N, the sum of the first n natural numbers is given by:
P(n): 1 + 2 + 3 + ... + n = n(n+1)/2

• Step I (Base Case): For n = 1,

  • LHS = 1
  • RHS = 1(1+1)/2 = 1(2)/2 = 1
  • Since LHS = RHS, P(1) is true.

• Step II (Inductive Hypothesis): Assume P(k) is true for some positive integer k.

  • Assume: 1 + 2 + 3 + ... + k = k(k+1)/2

• Step III (Inductive Step): We need to prove P(k+1) is true.

  • P(k+1) statement is: 1 + 2 + 3 + ... + k + (k+1) = (k+1)((k+1)+1)/2 = (k+1)(k+2)/2
  • Let's start with the LHS of P(k+1):
    LHS = (1 + 2 + 3 + ... + k) + (k+1)
  • Using the Inductive Hypothesis (P(k) is true), we replace the sum up to k:
    LHS = [k(k+1)/2] + (k+1)
  • Now, simplify algebraically:
    LHS = (k+1) [k/2 + 1]
    LHS = (k+1) [(k + 2)/2]
    LHS = (k+1)(k+2)/2
  • This is exactly the RHS of the P(k+1) statement.
  • Therefore, P(k+1) is true.

• Step IV (Conclusion): Since P(1) is true and we have shown that if P(k) is true then P(k+1) is also true, by the Principle of Mathematical Induction, the statement P(n): 1 + 2 + 3 + ... + n = n(n+1)/2 is true for all natural numbers n.

5. Important Points for Government Exams:

• Understand the logic behind PMI – why both steps are essential.
• Be comfortable with algebraic manipulation, especially in the Inductive Step.
• Recognize the types of problems solvable by PMI (sums, divisibility, inequalities).
• PMI proves a given formula/statement; it doesn't help you discover the formula.
• Pay close attention to the Base Case – sometimes it might start from n=2 or n=0 depending on the problem statement.
• The Inductive Hypothesis is a crucial assumption used to bridge the gap from k to k+1.

Multiple Choice Questions (MCQs):

1. The Principle of Mathematical Induction is used to prove statements for:
   a) Only n=1
   b) A finite set of integers
   c) All real numbers
   d) All natural numbers (or a subset starting from some integer)

2. In the Principle of Mathematical Induction, the first step is called:
   a) Inductive Hypothesis
   b) Inductive Step
   c) Base Case
   d) Conclusion Step

3. If P(n) is the statement "n(n+1) is even", what is the Base Case P(1)?
   a) 1(1+1) = 2, which is even. (True)
   b) k(k+1) is even.
   c) (k+1)(k+2) is even.
   d) 1(1+1) = 2, which is odd. (False)

4. In proving a statement P(n) by induction, the Inductive Step involves:
   a) Proving P(1) is true.
   b) Assuming P(k) is true and proving P(k+1) is true.
   c) Assuming P(k+1) is true and proving P(k) is true.
   d) Assuming P(n) is true for all n.

5. What is the role of the Inductive Hypothesis (Assuming P(k) is true)?
   a) It is the final conclusion.
   b) It verifies the base case.
   c) It is an assumption used as a tool to prove P(k+1).
   d) It proves the statement for n=k.

6. Let P(n) be the statement "3^n > n". If we assume P(k) is true (i.e., 3^k > k), what do we need to prove in the Inductive Step?
   a) 3^k > k+1
   b) 3^(k+1) > k
   c) 3^(k+1) > k+1
   d) 3^1 > 1

7. Consider the statement P(n): 1 + 3 + 5 + ... + (2n-1) = n². If P(k) is assumed true, what is P(k)?
   a) 1 + 3 + 5 + ... + (2k-1) = k²
   b) 1 + 3 + 5 + ... + (2(k+1)-1) = (k+1)²
   c) 1 + 3 + 5 + ... + (2k+1) = k²
   d) 1 + 3 + 5 + ... + (2k-1) = (k+1)²

8. For the statement P(n): "n³ - n is divisible by 3", which step confirms P(1)?
   a) Assume k³ - k is divisible by 3.
   b) Show (k+1)³ - (k+1) is divisible by 3.
   c) Check if 1³ - 1 = 0 is divisible by 3.
   d) Conclude P(n) is true for all n.

9. If someone proves P(1) is true and proves that P(k) true implies P(k+2) true, what can they conclude?
   a) P(n) is true for all natural numbers n.
   b) P(n) is true for all even natural numbers n.
   c) P(n) is true for all odd natural numbers n.
   d) P(n) is true for n=1 only.

10. A proof by induction fails if:
    a) The Base Case holds, but the Inductive Step fails.
    b) The Inductive Step holds, but the Base Case fails.
    c) Both the Base Case and the Inductive Step fail.
    d) All of the above.

Answer Key for MCQs:

1. d
2. c
3. a
4. b
5. c
6. c
7. a
8. c
9. c (Since the base is P(1) and it jumps by 2, it proves for 1, 3, 5, ...)
10. d

Study these notes carefully, focusing on understanding the process and logic. Practice applying the steps to different types of problems from your textbook. Good luck!