Principle of Mathematical Induction

Mathematical induction occupies a unique position in epistemology: while carrying the name "induction," it is in fact an absolute, deductive proof method of unquestionable mathematical validity.

• Empirical (Scientific) Induction: Observes a finite set of specific instances and infers a general law. For example, observing 1,000 white swans and concluding "all swans are white." This form of induction can never provide mathematical certainty, because a single counterexample (e.g., a black swan in Australia) destroys the hypothesis.
• Deductive Reasoning: Derives specific truths necessarily and logically from accepted general axioms or premises. Mathematical induction belongs completely to deductive logic: it proves that a statement holds for infinitely many numbers without examining each one individually.

A mathematical statement or proposition involving natural numbers is denoted by $P(n)$, where $n \in \mathbb{N} = \{1, 2, 3, 4, \dots\}$.

Example: Let $P(n)$ be the statement: $1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$.

• For $n = 1$: $P(1)$ is the assertion $1 = \frac{1(1 + 1)}{2} = 1$ (True).
• For $n = 2$: $P(2)$ is the assertion $1 + 2 = \frac{2(2 + 1)}{2} = 3$ (True).
• Verifying $P(1), P(2), \dots, P(100)$ does NOT prove the statement for all $n$, because it might fail at $n = 101$. Only the Principle of Mathematical Induction provides universal proof.

The Principle of Mathematical Induction is logically equivalent to the Well-Ordering Principle: if a statement $P(n)$ were false for some natural numbers, the set of counterexamples would possess a smallest member, leading directly to a contradiction of the inductive step.

The Principle of Mathematical Induction formalizes an algorithmic procedure to guarantee universal truth over the infinite set of natural numbers in exactly two steps.

To grasp the mechanics of mathematical induction intuitively, consider an endless line of dominoes stood on end, labeled $1, 2, 3, \dots, k, k + 1, \dots$:

• The Base Step: Pushing over the first domino ($P(1)$ falls).
• The Inductive Step: Ensuring the spacing is such that whenever any $k$-th domino falls, it must inevitably knock over the $(k + 1)$-th domino ($P(k) \implies P(k + 1)$).
• The Inevitable Conclusion: As a consequence of the two conditions, every domino in the infinite chain will fall!

Summation identities form the most frequent category of induction questions in WBCHSE board examinations.

In all series summation proofs, the inductive step follows a uniform, systematic algebraic pattern:

1. By hypothesis, the sum of the first $k$ terms is known: $S_k = f(k)$.
2. To find the sum of the first $(k + 1)$ terms, split the expression into the first $k$ terms plus the $(k + 1)$-th term: $$S_{k+1} = \underbrace{T_1 + T_2 + \dots + T_k}_{S_k} + T_{k+1} = f(k) + T_{k+1}$$
3. Substitute the inductive hypothesis for $S_k$, factor out common terms (never expand polynomials prematurely!), and simplify into $f(k + 1)$.

Another classic archetype involves fractions with products in denominators:

Proving that an expression $f(n)$ is divisible by a fixed integer $d$ for all $n \in \mathbb{N}$ requires a powerful algebraic decomposition strategy.

An expression $f(n)$ is divisible by an integer $d$ if and only if there exists an integer $\lambda$ such that:

When proving that $f(n)$ is divisible by $d$:

• Example A: $(x^n - y^n)$ is divisible by $(x - y)$ for all $n \in \mathbb{N}$. $$x^{k+1} - y^{k+1} = x \cdot x^k - y \cdot y^k = x(x^k - y^k) + y^k(x - y) = x[(x - y)\lambda] + y^k(x - y) = (x - y)[x\lambda + y^k]$$
• Example B: $(7^n - 3^n)$ is divisible by $4$ for all $n \in \mathbb{N}$. $$7^{k+1} - 3^{k+1} = 7 \cdot 7^k - 3 \cdot 3^k = 7(7^k - 3^k) + 4 \cdot 3^k = 7(4\lambda) + 4 \cdot 3^k = 4[7\lambda + 3^k]$$
• Example C: $(10^{2n-1} + 1)$ is divisible by $11$ for all $n \in \mathbb{N}$.

Inequality proofs require careful manipulation because inequalities, unlike equations, only transmit in one direction via transitivity.

Many mathematical statements are not true for $n = 1, 2, \dots$, but become true after a certain threshold integer $n_0 > 1$.

Example: $2^n < n!$ is false for $n = 1$ ($2 < 1$ false), $n = 2$ ($4 < 2$ false), and $n = 3$ ($8 < 6$ false). But for $n = 4$: $2^4 = 16 < 4! = 24$ (True!). Hence the base step begins at $\mathbf{n_0 = 4}$.

To prove $L(k + 1) < R(k + 1)$ from $L(k) < R(k)$:

Proof by Induction:

• For $n = 1$: $(1 + x)^1 = 1 + 1x$ (True with equality).
• Assume true for $n = k$: $(1 + x)^k \ge 1 + kx$. Since $x > -1 \implies (1 + x) > 0$, multiply both sides by $(1 + x)$: $$(1 + x)^{k+1} \ge (1 + kx)(1 + x) = 1 + x + kx + kx^2 = 1 + (k + 1)x + \underbrace{kx^2}_{\ge 0} \ge 1 + (k + 1)x$$
• Hence $P(k + 1)$ is true, completing the proof.

In advanced combinatorial and algebraic problems, the standard (weak) induction hypothesis is sometimes insufficient, necessitating the Principle of Strong Mathematical Induction.

Key Application: Proving the Fundamental Theorem of Arithmetic (every integer $n > 1$ can be factored into prime numbers). Factoring $k + 1 = a \cdot b$ requires inductive hypotheses on both $a$ and $b$, which are smaller than $k$, rather than merely on $k$.

Consider the infamous false "proof" that all horses have the same colour:

• Claim: In any set of $n$ horses, all horses have the same colour.
• Base Step: For $n = 1$, a set of 1 horse trivially has only one colour.
• Inductive Step: Consider a set of $k + 1$ horses $\{H_1, H_2, \dots, H_k, H_{k+1}\}$. Remove $H_{k+1}$; the remaining $k$ horses $\{H_1, \dots, H_k\}$ share the same colour by hypothesis. Next remove $H_1$; the remaining $k$ horses $\{H_2, \dots, H_{k+1}\}$ share the same colour. Since the two groups overlap, all $k+1$ horses must be the same colour!
• The Critical Fallacy: The argument fails when transitioning from $k = 1$ to $k + 1 = 2$! For $n = 2$, the two subsets are $\{H_1\}$ and $\{H_2\}$; they have NO OVERLAPPING HORSE. Thus, the domino chain is severed between $1$ and $2$.