Proof by Induction

Introduction: Why this method matters 🔍

students, in mathematics we often need to prove that a statement is true for every natural number $n$. That might sound impossible at first because there are infinitely many numbers to check. Proof by induction is a powerful method that helps us do exactly that. It is especially useful in Number and Algebra because many patterns in sequences, sums, divisibility, and algebraic identities depend on $n$.

By the end of this lesson, you should be able to:

• explain the key ideas and vocabulary of proof by induction,
• carry out an inductive proof step by step,
• understand how induction connects to sequences, series, and algebraic structure,
• recognize when induction is appropriate, and
• use induction to justify statements in IB Mathematics: Analysis and Approaches HL.

Think of induction like a row of dominoes 🁢. If the first domino falls, and each domino can knock over the next one, then all the dominoes will fall. In mathematics, the “dominoes” are the natural numbers.

The main idea of induction

A proof by induction has two essential parts:

1. Base case: Show the statement is true for the first relevant value, often $n=1$ or $n=0$.
2. Inductive step: Assume the statement is true for some arbitrary natural number $k$, then use that assumption to prove it is true for $k+1$.

This works because once the base case is true and every case leads to the next one, the truth spreads across all natural numbers.

The assumption that the statement is true for $n=k$ is called the inductive hypothesis.

A typical induction proof is written as follows:

• State the proposition clearly.
• Verify the base case.
• Assume the proposition is true for $n=k$.
• Use that assumption to prove the proposition for $n=k+1$.
• Conclude that the statement is true for all natural numbers from the starting value onward.

It is important not to confuse the inductive hypothesis with what we are trying to prove. In the inductive step, we are allowed to assume the statement for $k$ only because we are proving the statement for $k+1$.

A first example: a sum formula

Let us prove the formula

$$1+2+3+

$\cdots$+n=$\frac{n(n+1)}{2}$$$

for all $n\in \mathbb{N}$.

Step 1: Base case

For $n=1$, the left side is $1$, and the right side is

$$\frac{1(1+1)}{2}=\frac{2}{2}=1.$$

So the statement is true for $n=1$.

Step 2: Inductive hypothesis

Assume that for some $k\in\mathbb{N}$,

$$1+2+3+\cdots+k=\frac{k(k+1)}{2}.$$

Step 3: Prove the case $k+1$

Start with the left side for $n=k+1$:

$$1+2+3+\cdots+k+(k+1).$$

Using the inductive hypothesis, replace the first part:

$$\frac{k(k+1)}{2}+(k+1).$$

Factor out $k+1$:

$$\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{(k+1)(k+2)}{2}.$$

That is exactly the formula with $n=k+1$:

$$\frac{(k+1)((k+1)+1)}{2}.$$

So if the formula is true for $n=k$, it is true for $n=k+1$.

Conclusion

Since the base case is true and the truth passes from one natural number to the next, the formula is true for all $n\in\mathbb{N}$.

This result is a classic example of how induction supports work with series in Number and Algebra 📘.

Why the inductive step works

The inductive step is the heart of the method. It shows a logical chain:

$$P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots$$

Here, $P(n)$ means the statement is true for $n$.

If we prove two things:

• $P(1)$ is true, and
• for every $k\in\mathbb{N}$, $P(k)\Rightarrow P(k+1)$,

then all statements $P(n)$ must be true.

This is closely related to the well-ordering principle and the structure of the natural numbers. The natural numbers are arranged so that every number has a next number, which makes induction possible.

students, it helps to remember that induction is not “guessing” from examples. Checking $n=1,2,3,4$ may suggest a pattern, but only induction proves it for all $n$.

Another example: divisibility

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

This means we want to show

$$6 \mid (7^n-1).$$

Base case

For $n=1$,

$$7^1-1=6,$$

which is divisible by $6$.

Inductive hypothesis

Assume for some $k\in\mathbb{N}$ that

$$6\mid (7^k-1).$$

So there exists an integer $m$ such that

$$7^k-1=6m.$$

Inductive step

Now consider $7^{k+1}-1$:

$$7^{k+1}-1=7\cdot 7^k-1.$$

Rewrite it as

$$7(7^k-1)+6.$$

Using the inductive hypothesis, $7^k-1$ is divisible by $6$, so $7(7^k-1)$ is also divisible by $6$. Since $6$ is divisible by $6$, the sum is divisible by $6$.

Therefore, $6\mid(7^{k+1}-1)$.

So the statement is true for all $n\in\mathbb{N}$.

This kind of proof is very useful in number theory because it connects induction with divisibility rules and modular thinking.

Induction with algebraic identities

Induction can also prove algebraic formulas that involve powers. Consider

$$1+3+3^2+\cdots+3^{n-1}=\frac{3^n-1}{2}$$

for $n\in\mathbb{N}$.

The pattern on the left is a geometric series. A direct formula is often known, but induction provides a rigorous proof.

Base case

For $n=1$, the left side is just $1$, and the right side is

$$\frac{3^1-1}{2}=1.$$

Inductive hypothesis

Assume

$$1+3+3^2+\cdots+3^{k-1}=\frac{3^k-1}{2}.$$

Inductive step

For $n=k+1$,

$$1+3+3^2+\cdots+3^{k-1}+3^k.$$

Substitute the hypothesis:

$$\frac{3^k-1}{2}+3^k=\frac{3^k-1+2\cdot 3^k}{2}=\frac{3^{k+1}-1}{2}.$$

So the formula is true for $k+1$, and therefore for all $n\in\mathbb{N}$.

This shows how induction strengthens algebraic reasoning by confirming formulas for every term, not just the first few.

Common mistakes to avoid ⚠️

When writing induction proofs, students often make these errors:

• Forgetting the base case. Without it, the chain never starts.
• Assuming what you need to prove. In the inductive step, you may use the statement for $k$, but not for $k+1$ before proving it.
• Using examples instead of proof. Testing a few values does not prove the statement for all $n$.
• Not clearly linking $k$ and $k+1$. The step from one case to the next must be explicit.
• Algebra mistakes. Many induction proofs fail because of simplification errors, not because the idea is wrong.

A useful strategy is to write the statement for $k$ and $k+1$ side by side. This makes the transition easier to see.

How induction fits into Number and Algebra

Proof by induction sits at the center of several ideas in Number and Algebra:

• Sequences and series: Many formulas for arithmetic and geometric sums are proved by induction.
• Number systems: Induction helps prove facts about natural numbers, integers, and divisibility.
• Symbolic manipulation: It requires algebraic rearrangement and factorization.
• Patterns and generalization: It turns observed patterns into rigorous results.
• Proof: It develops logical reasoning, which is essential in higher-level mathematics.

In IB Mathematics: Analysis and Approaches HL, induction appears frequently when a result depends on a natural number parameter $n$. It is a standard tool for proving identities involving sums, powers, and recursive patterns.

Conclusion

Proof by induction is a structured way to prove statements for all natural numbers. It uses a base case to start the process and an inductive step to show that truth passes from $n=k$ to $n=k+1$. students, this makes induction one of the most important proof methods in Number and Algebra because it connects patterns, sequences, algebraic formulas, and number properties in a logically complete way ✅.

When you see a statement involving $n\in\mathbb{N}$, ask yourself whether induction might be appropriate. If the statement has a clear pattern that changes from one natural number to the next, induction is often the right tool.

Study Notes

• Proof by induction is used to prove statements for all natural numbers $n$.
• The two main parts are the base case and the inductive step.
• The inductive hypothesis assumes the statement is true for $n=k$.
• The goal of the inductive step is to prove the statement for $n=k+1$.
• Induction is like dominoes: once the first one falls and each one knocks over the next, all fall.
• Common uses include sums, sequences, divisibility, and algebraic identities.
• A proof by induction must be logically complete; checking only a few cases is not enough.
• Induction is an important part of Number and Algebra in IB Mathematics: Analysis and Approaches HL.