Mathematical Induction — Proving Infinite Truths

The Big Idea

How do you prove that a statement is true for every natural number — not just 1, 2, 3, but ALL of them, infinitely many?

Mathematical induction is the answer. It’s like a chain of dominoes: you show that the first domino falls (base case), and that whenever one domino falls, the next one falls too (inductive step). Then every domino must eventually fall.

This chapter appears in CBSE Class 11 (Chapter 4) and is straightforward once you get the format right. JEE Main rarely tests pure induction but the technique underlies many proofs across topics.

The Principle

The Principle of Mathematical Induction (PMI) states:

Let $P(n)$ be a statement involving the natural number $n$. If:

1. Base case: $P(1)$ is true (or $P(n_0)$ for some starting value $n_0$)
2. Inductive step: Whenever $P(k)$ is true for some arbitrary $k \geq 1$, then $P(k+1)$ is also true

Then $P(n)$ is true for all natural numbers $n \geq 1$ (or $n \geq n_0$).

Strong vs Weak Induction

Weak (simple) induction: Assumes $P(k)$ is true to prove $P(k+1)$.

Strong induction: Assumes $P(1), P(2), \ldots, P(k)$ are all true to prove $P(k+1)$. Useful when $P(k+1)$ depends not just on $P(k)$ but on multiple earlier cases (e.g., Fibonacci-type recurrences).

For CBSE and most JEE problems, weak induction suffices.

Worked Examples

Example 1 — Sum Formula (CBSE Classic)

Prove: $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for all $n \in \mathbb{N}$.

Step 1: State $P(n)$

$P(n): \displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$

Step 2: Base Case — $P(1)$

LHS $= 1$. RHS $= \dfrac{1 \times 2}{2} = 1$. LHS = RHS, so $P(1)$ is true. ✓

Step 3: Inductive Hypothesis

Assume $P(k)$ is true for some $k \geq 1$:

Step 4: Prove $P(k+1)$

We need to show: $1 + 2 + \cdots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}$

Starting from the left:

This is exactly the RHS of $P(k+1)$. ✓

Step 5: Conclusion

By the Principle of Mathematical Induction, $P(n)$ is true for all $n \in \mathbb{N}$.

Example 2 — Sum of Squares

Prove: $1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ for all $n \in \mathbb{N}$.

Base case ($n=1$): LHS $= 1$, RHS $= \dfrac{1 \cdot 2 \cdot 3}{6} = 1$. ✓

Inductive hypothesis: Assume $\displaystyle\sum_{k=1}^{m} k^2 = \frac{m(m+1)(2m+1)}{6}$ for some $m \geq 1$.

Inductive step: Show the formula holds for $m+1$.

This is $P(m+1)$. ✓ Conclusion: true for all $n \in \mathbb{N}$.

Example 3 — Divisibility Proof

Prove: $7^n - 1$ is divisible by 6 for all $n \in \mathbb{N}$.

Base case ($n=1$): $7^1 - 1 = 6 = 6 \times 1$. Divisible by 6. ✓

Inductive hypothesis: Assume $6 \mid (7^k - 1)$, i.e., $7^k - 1 = 6m$ for some integer $m$.

So $7^k = 6m + 1$.

Inductive step: Show $6 \mid (7^{k+1} - 1)$.

Since $7m + 1$ is an integer, $6 \mid (7^{k+1} - 1)$. ✓

Conclusion: $7^n - 1$ is divisible by 6 for all $n \in \mathbb{N}$.

Example 4 — Inequality Proof (JEE Level)

Prove: $2^n > n$ for all $n \in \mathbb{N}$.

Base case ($n=1$): $2^1 = 2 > 1$. ✓

Inductive hypothesis: Assume $2^k > k$ for some $k \geq 1$.

Inductive step: Show $2^{k+1} > k+1$.

We need $2k > k+1$, which means $k > 1$. For $k \geq 2$, this is true.

For $k = 1$ (base case already checked): $2^2 = 4 > 2$. ✓

So for $k \geq 1$: $2^{k+1} = 2 \cdot 2^k > 2k \geq k + 1$ (since $k \geq 1 \Rightarrow 2k \geq k+1$).

Therefore $2^{k+1} > k+1$. ✓ Conclusion holds for all $n \geq 1$.

Example 5 — De Moivre’s Theorem Preview

Prove: $(\cos\theta + i\sin\theta)^n = \cos(n\theta) + i\sin(n\theta)$ for all $n \in \mathbb{N}$.

Base case ($n=1$): $(\cos\theta + i\sin\theta)^1 = \cos\theta + i\sin\theta = \cos(1\cdot\theta) + i\sin(1\cdot\theta)$. ✓

Inductive hypothesis: Assume $(\cos\theta + i\sin\theta)^k = \cos(k\theta) + i\sin(k\theta)$.

Inductive step:

This is $P(k+1)$. ✓ De Moivre’s theorem is proved.

Common Mistakes to Avoid

Practice Questions

Q1. Prove by induction: $1 + 3 + 5 + \cdots + (2n-1) = n^2$.

Q2. Prove: $n^3 + 2n$ is divisible by 3 for all $n \in \mathbb{N}$.

Q3. Prove: $2^n \geq n+1$ for all $n \geq 1$.

Q4. Prove by induction: $1 \cdot 2 + 2 \cdot 3 + \cdots + n(n+1) = \dfrac{n(n+1)(n+2)}{3}$.

FAQs

Can induction be used to prove something false? If you make an error in the inductive step, you can “prove” false statements. A famous example is the “all horses are the same colour” pseudo-proof, where the inductive step secretly fails at $n=2$. This is why carefully writing out the proof step-by-step matters.

What’s the difference between proof by induction and proof by contradiction? Induction proves statements about all natural numbers by establishing a chain of implications. Contradiction assumes the statement is false and derives a logical impossibility. Both are valid proof techniques; the right one depends on the problem structure. Induction shines for recursive formulas and divisibility; contradiction works well for irrationality proofs.

What if the base case is $n = 0$ or $n = 2$? The base case doesn’t have to be $n = 1$. If you want to prove $P(n)$ for all $n \geq 0$, your base case is $P(0)$. If the statement only holds for $n \geq 2$, start with $P(2)$ as the base case. The conclusion then reads “true for all $n \geq 2$.”

Does induction prove a formula or discover it? Induction only proves a formula — it cannot discover it. You must already know (or guess) the formula before using induction. Discovery usually comes from pattern observation or other techniques (like the Gauss trick for sum of natural numbers).

Is there a “backward” version of induction? Yes — “downward induction” starts from a large value and proves the statement for smaller values. This is rarely tested in CBSE/JEE but is used in some advanced proofs (like AM-GM for all $n$ using Cauchy’s forward-backward induction).

Additional Worked Examples

Example 6 — Product formula

Prove: $\left(1 + \frac{1}{1}\right)\left(1 + \frac{1}{2}\right)\cdots\left(1 + \frac{1}{n}\right) = n + 1$ for all $n \in \mathbb{N}$.

Base case ($n=1$): $\left(1 + \frac{1}{1}\right) = 2 = 1 + 1$. ✓

Inductive hypothesis: Assume the product up to $k$ equals $k + 1$.

Inductive step: Multiply both sides by $\left(1 + \frac{1}{k+1}\right)$:

This is $P(k+1)$. ✓

Example 7 — Recurrence relation

Prove: If $a_1 = 1$ and $a_{n+1} = 2a_n + 1$, then $a_n = 2^n - 1$ for all $n \geq 1$.

Base case: $a_1 = 2^1 - 1 = 1$. ✓

Inductive hypothesis: $a_k = 2^k - 1$.

Inductive step: $a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1$. ✓

Common Induction Patterns in JEE

Additional Practice Questions

Q5. Prove: $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}$.

Q6. Prove that $n! > 2^n$ for all $n \geq 4$.