krit.club logo

Principle of Mathematical Induction - Simple Applications

Grade 11CBSE

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

🔑Concepts

•

Principle of Mathematical Induction (PMI) is a powerful proof technique used to establish the validity of mathematical statements for all natural numbers n∈Nn \in \mathbb{N}. It acts like a logical chain reaction.

•

The Base Case involves verifying that the statement P(n)P(n) is true for the initial value, typically n=1n = 1. Visually, this is equivalent to checking if the first rung of a ladder is solid enough to step on or if the first domino in a line can be tipped over.

•

The Inductive Hypothesis is the assumption that the statement P(n)P(n) holds true for some arbitrary natural number kk, denoted as P(k)P(k). We treat this as a given fact to bridge the gap to the next term.

•

The Inductive Step is the core of the proof where we demonstrate that if P(k)P(k) is true, then P(k+1)P(k+1) must necessarily be true. This establishes the 'link' between consecutive numbers. If you visualize a ladder, this step proves that from any rung kk, you have the ability to reach rung k+1k+1.

•

The Domino Effect is a common visual metaphor for PMI: If you have an infinite row of dominos, proving the base case is like knocking over the first domino. Proving the inductive step is like ensuring that if any domino falls, it will hit and knock over the next one. Consequently, all dominos will fall.

•

Divisibility Applications involve proving that an expression f(n)f(n) is divisible by a constant dd. In the inductive step, we manipulate f(k+1)f(k+1) to show it can be expressed as the sum of f(k)f(k) and another term clearly divisible by dd.

•

Inequality Applications use PMI to show that one expression is always greater or less than another for n≥n0n \geq n_0. This requires careful algebraic manipulation in the inductive step to maintain the direction of the inequality sign.

📐Formulae

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

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

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

Sum of an Arithmetic Progression (AP): a+(a+d)+(a+2d)+...+[a+(n−1)d]=n2[2a+(n−1)d]a + (a+d) + (a+2d) + ... + [a+(n-1)d] = \frac{n}{2} [2a + (n-1)d]

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

General form of PMI: If P(1)P(1) is true and P(k)  ⟹  P(k+1)P(k) \implies P(k+1), then P(n)P(n) is true ∀n∈N\forall n \in \mathbb{N}.

💡Examples

Problem 1:

Prove by mathematical induction that for all n∈Nn \in \mathbb{N}: 1+3+5+...+(2n−1)=n21 + 3 + 5 + ... + (2n-1) = n^2

Solution:

Step 1: Base Case. For n=1n=1, LHS = 2(1)−1=12(1)-1 = 1 and RHS = 12=11^2 = 1. Since LHS = RHS, P(1)P(1) is true. \nStep 2: Inductive Hypothesis. Assume P(k)P(k) is true for some k∈Nk \in \mathbb{N}. That is, 1+3+5+...+(2k−1)=k21 + 3 + 5 + ... + (2k-1) = k^2. \nStep 3: Inductive Step. We need to prove P(k+1)P(k+1) is true: 1+3+5+...+(2k−1)+(2(k+1)−1)=(k+1)21 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)^2. \nStarting with LHS of P(k+1)P(k+1): \n[1+3+5+...+(2k−1)]+(2k+2−1)[1 + 3 + 5 + ... + (2k-1)] + (2k+2-1) \nUsing our hypothesis, we substitute k2k^2 for the sum in brackets: \nk2+(2k+1)k^2 + (2k+1) \nThis simplifies to (k+1)2(k+1)^2, which is the RHS. \nThus, P(k+1)P(k+1) is true whenever P(k)P(k) is true. By the principle of mathematical induction, the statement is true for all n∈Nn \in \mathbb{N}.

Explanation:

This example demonstrates the summation application of PMI. We verify the smallest case, assume the formula works for kk, and use that assumption to prove it works for k+1k+1 by adding the (k+1)th(k+1)^{th} term to both sides.

Problem 2:

Prove that 7n−3n7^n - 3^n is divisible by 44 for every natural number nn.

Solution:

Step 1: Base Case. For n=1n=1, 71−31=47^1 - 3^1 = 4, which is divisible by 44. Thus P(1)P(1) is true. \nStep 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. \nStep 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. \n7k+1−3k+1=7⋅7k−3k+17^{k+1} - 3^{k+1} = 7 \cdot 7^k - 3^{k+1} \nSubstitute 7k=4m+3k7^k = 4m + 3^k from the hypothesis: \n7(4m+3k)−3k+17(4m + 3^k) - 3^{k+1} \n=28m+7⋅3k−3⋅3k= 28m + 7 \cdot 3^k - 3 \cdot 3^k \n=28m+(7−3)⋅3k=28m+4⋅3k= 28m + (7-3) \cdot 3^k = 28m + 4 \cdot 3^k \n=4(7m+3k)= 4(7m + 3^k) \nSince 4(7m+3k)4(7m + 3^k) is a multiple of 44, P(k+1)P(k+1) is true. By PMI, the statement is true for all n∈Nn \in \mathbb{N}.

Explanation:

This is a divisibility application. The strategy is to isolate one power from the k+1k+1 expression and substitute the inductive hypothesis to reveal a common factor of the divisor.