Q.If $a$ and $b$ are distinct integers, prove that $a - b$ is a factor of $a^n - b^n$, whenever $n$ is a positive integer. [Hint: write $a^n = (a - b + b)^n$ and expand]

Proof by Induction: From Dominoes to Certainty

Imagine you have an infinite line of dominoes standing upright. You want to be absolutely sure that every single domino will fall. How would you prove it?

You'd need two things:

1. The first domino falls — you push it.
2. If any domino falls, the next one falls too — they are close enough to knock each other over.

That's it. If both conditions hold, you know — without checking each domino individually — that every domino will eventually fall. This is the core intuition behind proof by induction.

The Problem Induction Solves

Many mathematical statements involve natural numbers ($1, 2, 3, \dots$) and claim something is true for all of them. For example:

The sum of the first $n$ odd numbers equals $n^2$.

You could check: $1 = 1^2$, $1+3 = 2^2$, $1+3+5 = 3^2$, $1+3+5+7 = 4^2$... but you can never check infinitely many cases. Induction gives you a way to prove it in just two steps.

The Precise Structure

Let $P(n)$ be a statement about a natural number $n$ (like "the sum of the first $n$ odd numbers is $n^2$"). To prove $P(n)$ is true for all $n \geq 1$, you need:

The two parts have names:

1. Base case: Prove $P(1)$ is true. (The first domino falls.)
2. Inductive step: Assume $P(k)$ is true for some arbitrary $k \geq 1$, and prove $P(k+1)$ follows. (If domino $k$ falls, domino $k+1$ falls too.)

The assumption "$P(k)$ is true" is called the inductive hypothesis.

A Worked Example

Let's prove: $1 + 3 + 5 + \dots + (2n-1) = n^2$ for all $n \geq 1$.

Base case ($n=1$):

Left side: $1$

Right side: $1^2 = 1$

So $P(1)$ is true.

Inductive step:

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

We want to prove $P(k+1)$:

Start from the left side of $P(k+1)$:

Replace the bracketed sum using the inductive hypothesis:

Simplify:

That's exactly the right side of $P(k+1)$. So $P(k) \implies P(k+1)$ is proved.

Since both conditions hold, $P(n)$ is true for all $n \geq 1$.

Why It Works (The Logic)

Induction is a domino chain of implications:

• $P(1)$ is true (base).
• $P(1) \implies P(2)$ (inductive step with $k=1$), so $P(2)$ is true.
• $P(2) \implies P(3)$ (inductive step with $k=2$), so $P(3)$ is true.
• $P(3) \implies P(4)$, so $P(4)$ is true.
• ... and so on, forever.

You never need to check infinitely many cases. The inductive step acts as a "machine" that, given any true $P(k)$, produces $P(k+1)$. The base case feeds the machine the first truth, and the machine keeps running forever.

When to Use Induction

Induction works when:

• The statement is about natural numbers (or any well-ordered set).
• The statement for $n+1$ can be expressed in terms of the statement for $n$.

It's especially useful for:

• Summation formulas (like the example above)
• Divisibility proofs (e.g., "$n^3 - n$ is divisible by 3")
• Inequalities (e.g., "$2^n > n^2$ for $n \geq 5$")
• Recursive definitions (e.g., Fibonacci numbers)

The Principle of Mathematical Induction is its own dedicated chapter in the NCERT Class 11 Mathematics syllabus, and "proof by induction steps and examples" is a frequently searched topic among students preparing for CBSE boards and competitive-exam logic-based questions. Since summation-formula proofs are a classic exam format, this concept regularly appears in "mathematical induction important questions" for JEE Main revision.