Induction

Induction is a method for proving statements that hold for all natural numbers.

The idea is to show that if a statement holds for the first number, and if it holds for an arbitrary number \( \large k \), then it must also hold for \( \large k+1 \). In this way, one shows that the statement holds for all \( \large n \).

 

Induction works like a row of dominoes: If the first piece falls (the base step), and each piece makes the next one fall (the induction step), then all pieces in the row will fall.

 

Procedure

A proof by induction usually consists of three steps:

 

1. Base: Show that the statement holds for the first natural number, typically \( \large n=1 \).
2. Induction hypothesis: Assume that the statement holds for an arbitrary \( \large n=k \).
3. Induction step: Use the assumption to show that the statement also holds for \( \large n=k+1 \).

 

 

Example 1

We want to prove by induction that the sum of the first \( \large n \) natural numbers is

 

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

 

Base:

 

For \( \large n=1 \) we get \( \large 1 = \frac{1 \cdot (1+1)}{2} = 1 \). The statement is true.

 

Induction hypothesis:

 

Assume that the statement holds for \( \large n=k \):

 

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

 

Induction step:

 

For \( \large n=k+1 \) we get:

 

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

 

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

 

Which is the same formula with \( \large n=k+1 \). Thus the statement is proven for all \( \large n \).

 

 

Example 2

We want to prove by induction that \( \large 5^n - 2^n \) is always divisible by 3 for all \( \large n \in \mathbb{N} \).

 

Base:

 

For \( \large n=1 \) we get \( \large 5^1 - 2^1 = 3 \), which is divisible by 3.

 

Induction hypothesis:

 

Assume that the statement holds for \( \large n=k \):

 

$$ \large 5^k - 2^k = 3m $$

 

for some integer \( \large m \).

 

Induction step:

 

For \( \large n=k+1 \) we start by rewriting the powers:

 

$$ \large 5^{k+1} - 2^{k+1} = 5 \cdot 5^k - 2 \cdot 2^k $$

 

Now we want to collect a term with \( \large (5^k - 2^k) \). Therefore we rewrite \( \large -2 \cdot 2^k \) as \( \large -5 \cdot 2^k + 3 \cdot 2^k \). Then we get:

 

$$ \large 5 \cdot 5^k - 2 \cdot 2^k = 5 \cdot 5^k - 5 \cdot 2^k + 3 \cdot 2^k $$

 

Now the first two terms can be collected in a parenthesis:

 

$$ \large = (5^k - 2^k)\cdot 5 + 3 \cdot 2^k $$

 

By the induction hypothesis \( \large 5^k - 2^k \) is divisible by 3, and \( \large 3 \cdot 2^k \) is clearly also divisible by 3. Thus the entire expression is divisible by 3, and the statement is proven for \( \large n=k+1 \).

 

 

Proofs by induction are a central tool in mathematics. They are used to prove formulas, properties of sequences, divisibility and much more.

The method shows how a statement can hold for infinitely many numbers by connecting each step in the sequence logically with the next one.