Mathematical induction — principle, steps, problems: Foundations

This page assumes you know nothing about the notation in the parent note Mathematical Induction. We build every symbol from the ground up, in the order you need them.

0. What is a "natural number"?

The picture: an endless row of evenly spaced dots stretching to the right. Each dot is one number; there is a first dot, but no last dot.

Figure — Mathematical induction — principle, steps, problems

Why the topic needs it. Induction is a tool for proving something is true for all of these — an infinite list. If the list were finite we could just check every case by hand. The whole point is that we can't, so we need a cleverer argument.

1. The symbol $n$ — a "stand-in" for any number

The picture: think of $n$ as an empty box $□$ . You may drop $1$ into the box, or $7$ , or $1000$ . The sentence around the box must stay meaningful for whatever you drop in.

Why the topic needs it. We want one single sentence that covers all of $1, 2, 3, \dots$ at once. A variable lets us write that one sentence instead of infinitely many.

2. The symbol $P (n)$ — a statement that may be true or false

The picture: $P$ is a machine. You feed it a number $n$ ; out comes a light that is either green (true) or red (false).

Why the topic needs it. Induction's goal is exactly: "show the light is green for every input $n$ ." Naming that goal $P (n)$ lets us talk about it precisely.

3. The symbols $k$ and $k + 1$ — "some domino" and "the next one"

The picture: in the endless row of dots, put your finger on one dot and call it $k$ . The dot immediately to its right is $k + 1$ .

Why the topic needs it. The heart of induction is the sentence "if domino $k$ falls, then domino $k + 1$ falls." We need names for "this domino" ( $k$ ) and "the next domino" ( $k + 1$ ) to even write that sentence.

4. The arrow $\Rightarrow$ — "implies"

The picture: two dominoes standing close. The arrow is the gap being small enough that a falling left domino is guaranteed to hit the right one. The arrow says nothing about whether the left one actually fell — only "if it falls, the right one falls."

Why the topic needs it. The entire inductive step is one implication: $P (k) \Rightarrow P (k + 1)$ . Understanding that this is a conditional promise (not an assertion that $P (k)$ is true) is what saves you from Trap 3 in the parent note.

5. The sum " $1 + 2 + \dots + n$ " and the $Σ$ shorthand

The picture: a row of bars of heights $1, 2, \dots, n$ . The sum is the total area of all the bars stacked.

Why the topic needs it. Half the induction examples are sum formulas. When we "add the next term to both sides," that next term is precisely the $(k + 1)$ -th bar — the sum symbol makes "the next term" unambiguous: going from $\sum_{i = 1}^{k}$ to $\sum_{i = 1}^{k + 1}$ just glues on one more bar, $(k + 1)$ .

6. The bar $∣$ — "divides"

The picture: try to tile a strip of length $b$ using identical tiles of length $a$ . If they fit perfectly with no gap, $a ∣ b$ .

Why the topic needs it. Worked Example 3 in the parent proves " $6 ∣ n^{3} - n$ ". To carry the divisibility across the step we rewrite the new expression as (old divisible chunk) + (leftover), then show the leftover is also a multiple of $6$ .

7. The inequality signs $>$ , $\geq$

Why the topic needs it. Example 4 proves the inequality $2^{n} > n$ . Notice a subtlety used there: to chain $2^{k + 1} > 2 k \geq k + 1$ we need both a strict $>$ and a " $\geq$ "; mixing them correctly is what makes the step valid.

8. Powers: $2^{n}$ , $n^{2}$ , $n^{3}$

Why the topic needs it. Sum-of-squares and the inequality $2^{n} > n$ both live on these. The key algebra move — factoring out a common $(k + 1)$ — relies on comfort with expanding powers like $(k + 1)^{3}$ .

9. The Well-Ordering Principle — the hidden engine

The picture: the row of dots has a leftmost dot. Any sub-collection you circle, however scattered, still has a leftmost circled dot.

Why the topic needs it. This is why induction works. If $P (n)$ failed anywhere, WOP hands you a smallest failing number $m$ ; the base case rules out $m = n_{0}$ , and the inductive step forces $P (m)$ true — contradiction. See Well-Ordering Principle for the full argument.

Prerequisite map

Equipment checklist

State what each symbol means before moving on:

What does

n \in N

mean?

n

is a natural (counting) number

1, 2, 3, \dots

What is

P (n)

A statement about

n

that becomes true or false once a specific number is plugged in — not a number itself.

Why do we use a separate letter

k

instead of

n

in the inductive step?

k

is one fixed number we zoom into;

n

ranges over all numbers. Keeping them apart avoids assuming what we want to prove.

What does

k + 1

picture as?

The dot immediately to the right of

k

— the "next domino."

What does

A \Rightarrow B

claim, and what does it NOT claim?

It claims "if

A

then

B

." It does NOT claim

A

is actually true.

What does

6 ∣ n^{3} - n

mean?

n^{3} - n

is an exact multiple of

6

(no remainder).

6 ∣ 0

true?

Yes —

0 = 6 \times 0

, so

0

is a multiple of every number.

Difference between

n^{2}

and

2^{n}

n^{2} = n \times n

;

2^{n}

2

multiplied by itself

n

times. Very different growth.

What does going from

\sum_{i = 1}^{k}

\sum_{i = 1}^{k + 1}

add?

Exactly one more term,

(k + 1)

— glue on the last bar.

What does the Well-Ordering Principle guarantee?

Every non-empty set of naturals has a smallest element — the engine behind induction.