krit.club logo

Algebra - Principle of Mathematical Induction

Grade 11ICSE

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

Mathematical Induction is a proof technique used to validate a statement P(n)P(n) for all natural numbers n∈{1,2,3,...}n \in \{1, 2, 3, ...\}. Visually, this process is often compared to a 'Domino Effect'—if you can knock down the first domino and ensure that any falling domino knocks down the next, the entire infinite row will fall.

•

The Base Case involves proving that the statement P(n)P(n) holds true for the smallest possible value in the domain, usually n=1n=1. This represents the first domino in the sequence being tipped over. If the formula is P(1)P(1), you calculate the Left Hand Side (LHS) and Right Hand Side (RHS) separately to check if they are equal.

•

The Inductive Hypothesis is the assumption that the statement P(n)P(n) is true for some arbitrary positive integer n=kn=k. We write out the expression as P(k)P(k) and treat it as a known fact or 'given' equation to be used in the next step.

•

The Inductive Step is the logical core where we prove that if P(k)P(k) is true, then P(k+1)P(k+1) must also be true. Visually, this is proving the link between any two adjacent dominoes. You start with the expression for P(k+1)P(k+1), substitute the inductive hypothesis, and algebraically manipulate it to match the required form for k+1k+1.

•

PMI is applied across three main categories in the ICSE syllabus: Series identities (sums of numbers), Divisibility properties (proving an expression is a multiple of a certain number), and Inequalities (comparing growth rates of expressions).

•

A formal conclusion is required after completing the steps. It states that since P(1)P(1) is true and the truth of P(k)P(k) implies the truth of P(k+1)P(k+1), then by the Principle of Mathematical Induction, P(n)P(n) is true for all n∈Nn \in \mathbb{N}.

📐Formulae

Sum of first nn natural numbers: ∑i=1ni=n(n+1)2\sum_{i=1}^{n} i = \frac{n(n+1)}{2}

Sum of squares of first nn natural numbers: ∑i=1ni2=n(n+1)(2n+1)6\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}

Sum of cubes of first nn natural numbers: ∑i=1ni3=[n(n+1)2]2\sum_{i=1}^{n} i^3 = \left[\frac{n(n+1)}{2}\right]^2

Sum of first nn odd numbers: 1+3+5+...+(2n−1)=n21 + 3 + 5 + ... + (2n-1) = n^2

Sum of a Geometric Series: a+ar+ar2+...+arn−1=a(rn−1)r−1a + ar + ar^2 + ... + ar^{n-1} = \frac{a(r^n - 1)}{r - 1}

Divisibility Notation: If aa divides bb, then b=a⋅mb = a \cdot m for some integer mm.

💡Examples

Problem 1:

Using the principle of mathematical induction, prove that: 1+3+5+...+(2n−1)=n21 + 3 + 5 + ... + (2n-1) = n^2 for all n∈Nn \in \mathbb{N}.

Solution:

  1. Base Case: Let n=1n=1. LHS =2(1)−1=1= 2(1)-1 = 1. RHS =12=1= 1^2 = 1. Since LHS = RHS, P(1)P(1) is true.
  2. Inductive Hypothesis: Assume P(k)P(k) is true for some k∈Nk \in \mathbb{N}: 1+3+5+...+(2k−1)=k21 + 3 + 5 + ... + (2k-1) = k^2.
  3. Inductive Step: We need to prove P(k+1)P(k+1) is true, i.e., 1+3+5+...+(2k−1)+[2(k+1)−1]=(k+1)21 + 3 + 5 + ... + (2k-1) + [2(k+1)-1] = (k+1)^2. From the hypothesis, we know the sum of the first kk terms is k2k^2. Adding the (k+1)th(k+1)^{th} term: LHS=k2+(2k+2−1)LHS = k^2 + (2k+2-1) LHS=k2+2k+1LHS = k^2 + 2k + 1 LHS=(k+1)2LHS = (k+1)^2 This is equal to the RHS of P(k+1)P(k+1).
  4. Conclusion: Since P(1)P(1) is true and P(k)  ⟹  P(k+1)P(k) \implies P(k+1), the statement is true for all n∈Nn \in \mathbb{N} by PMI.

Explanation:

This example demonstrates a series summation proof. The key is to substitute the assumed sum for kk terms into the expression for k+1k+1 terms and then use algebraic factoring to reach the target square form.

Problem 2:

Prove that 7n−3n7^n - 3^n is divisible by 44 for all n∈Nn \in \mathbb{N}.

Solution:

  1. Base Case: For n=1n=1, 71−31=47^1 - 3^1 = 4, which is divisible by 44. So P(1)P(1) is true.
  2. Inductive Hypothesis: Assume P(k)P(k) is true, i.e., 7k−3k=4m7^k - 3^k = 4m for some integer mm. This implies 7k=4m+3k7^k = 4m + 3^k.
  3. Inductive Step: We must show P(k+1)P(k+1) is true, i.e., 7k+1−3k+17^{k+1} - 3^{k+1} is divisible by 44. 7k+1−3k+1=7⋅7k−3⋅3k7^{k+1} - 3^{k+1} = 7 \cdot 7^k - 3 \cdot 3^k Substitute 7k=4m+3k7^k = 4m + 3^k: =7(4m+3k)−3⋅3k= 7(4m + 3^k) - 3 \cdot 3^k =28m+7⋅3k−3⋅3k= 28m + 7 \cdot 3^k - 3 \cdot 3^k =28m+4⋅3k= 28m + 4 \cdot 3^k =4(7m+3k)= 4(7m + 3^k) Since 4(7m+3k)4(7m + 3^k) is a multiple of 44, P(k+1)P(k+1) is true.
  4. Conclusion: By PMI, 7n−3n7^n - 3^n is divisible by 44 for all n∈Nn \in \mathbb{N}.

Explanation:

In divisibility problems, the trick is to break down the (k+1)(k+1) expression so you can substitute the kk assumption. Factoring out the divisor (4 in this case) at the end completes the proof.