krit.club logo

Principle of Mathematical Induction - The Principle of Mathematical Induction

Grade 11CBSE

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

🔑Concepts

•

Mathematical Induction is a deductive technique used to prove a statement, formula, or theorem that is asserted about every natural number n∈Nn \in \mathbb{N}. It transforms a potentially infinite set of cases into a two-step logical verification.

•

The Domino Analogy: Visualizing PMI as a row of standing dominoes is helpful. If you can knock down the first domino (Base Case) and ensure that if any domino falls, it will knock down the next one (Inductive Step), then you can conclude that all dominoes in the infinite sequence will eventually fall.

•

Step 1 - The Base Case: This involves proving that the statement P(n)P(n) is true for the first natural number in the sequence, usually n=1n=1. Visually, this is like checking if the 'first' point of a staircase is reachable.

•

Step 2 - The Inductive Hypothesis: Here, we assume that the statement P(n)P(n) is true for some arbitrary natural number n=kn = k, where k≥1k \ge 1. This is the 'bridge' we build to reach the next level.

•

Step 3 - The Inductive Step: Using the assumption from the hypothesis, we must prove that the statement is true for n=k+1n = k+1. If P(k)  ⟹  P(k+1)P(k) \implies P(k+1), the proof is complete by the Principle of Mathematical Induction.

•

Range of Validity: While most problems start at n=1n=1, the principle can be adapted to start at any integer n0n_0. In such cases, the base case is verified for P(n0)P(n_0) and the induction proceeds for all n≥n0n \ge n_0.

•

Application to Inequalities and Divisibility: PMI is not limited to series. It is frequently used to prove inequalities like 2n>n2^n > n or divisibility properties like (xn−yn)(x^n - y^n) being divisible by (x−y)(x - y). In these cases, the logic remains identical: check the base, assume kk, and derive k+1k+1.

📐Formulae

Sum of first nn natural numbers: 1+2+3+...+n=n(n+1)21 + 2 + 3 + ... + n = \frac{n(n + 1)}{2}

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

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

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

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

Divisibility Rule: If P(k)P(k) is f(k)=d⋅mf(k) = d \cdot m (where dd is the divisor), then prove f(k+1)=d⋅m′f(k+1) = d \cdot m'

💡Examples

Problem 1:

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

Solution:

Step 1: Let P(n)P(n) be the statement 1+3+5+...+(2n−1)=n21 + 3 + 5 + ... + (2n - 1) = n^2. 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. \Step 2: 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. \Step 3: We need to prove P(k+1)P(k+1) is true, which is 1+3+5+...+(2k−1)+[2(k+1)−1]=(k+1)21 + 3 + 5 + ... + (2k - 1) + [2(k+1) - 1] = (k+1)^2. \Starting from the LHS: (1+3+5+...+2k−1)+(2k+1)(1 + 3 + 5 + ... + 2k - 1) + (2k + 1). \Substitute the hypothesis: k2+(2k+1)k^2 + (2k + 1). \This simplifies to k2+2k+1k^2 + 2k + 1, which is (k+1)2(k+1)^2. \Thus, P(k+1)P(k+1) is true whenever P(k)P(k) is true. By PMI, the statement is true for all n∈Nn \in \mathbb{N}.

Explanation:

We first verified the smallest case, assumed the relation holds for a general term kk, and used algebraic expansion to show that adding the next odd term results in the square of the next integer.

Problem 2:

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

Solution:

Step 1: Let P(n):7n−3nP(n): 7^n - 3^n is divisible by 44. For n=1n=1, 71−31=47^1 - 3^1 = 4, which is divisible by 44. So P(1)P(1) is true. \Step 2: Assume P(k)P(k) is true, so 7k−3k=4m7^k - 3^k = 4m for some integer mm. This implies 7k=4m+3k7^k = 4m + 3^k. \Step 3: Prove P(k+1)P(k+1) is true: 7k+1−3k+17^{k+1} - 3^{k+1}. \We can write this as: 7⋅7k−3k+17 \cdot 7^k - 3^{k+1}. \Substitute 7k7^k from the hypothesis: 7(4m+3k)−3k+17(4m + 3^k) - 3^{k+1}. \Expand: 28m+7(3k)−3(3k)28m + 7(3^k) - 3(3^k). \Factor out 3k3^k: 28m+(7−3)3k=28m+4(3k)28m + (7-3)3^k = 28m + 4(3^k). \Factor out 4: 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. By PMI, 7n−3n7^n - 3^n is divisible by 44 for all n∈Nn \in \mathbb{N}.

Explanation:

In divisibility proofs, the key is to express the (k+1)(k+1) term in a way that allows you to substitute the assumption P(k)P(k) and then factor out the divisor.