Foundations — Strong induction

This page is a toolbox. The parent note Strong induction freely uses symbols like $P(n)$, $n_0$, $k<n$, $\Rightarrow$, $⟺$, $\forall$, $ab$, $a_n$, $■$. If any of those looks like a squiggle, read here first, then return.

0. The most basic picture: the number line of "counting numbers"

Everything in this topic lives on the integers — the whole numbers with no fractions:

$\dots ,-2,-1,0,1,2,3,4,\dots$

But strong induction almost always starts at some point and marches rightward forever. So the real playground is a line of evenly spaced dots stretching to the right with no end.

1. The symbol $n$ — a "slot" that any integer can fill

The letter $n$ is not a fixed number. It is a placeholder: a box you are allowed to drop any integer into.

2. The symbols $\ge$ and $<$ — "which dots are we talking about?"

We rarely want all integers — usually only those from a starting dot rightward.

• $n\ge n_0$ reads "$n$ is greater than or equal to $n_0$." Picture: $n$ sits on or to the right of the dot $n_0$.
• $k<n$ reads "$k$ is strictly less than $n$." Picture: $k$ sits strictly to the left of $n$ — never on top of it.

3. The symbol $P(n)$ — a statement that is either true or false

This is the heart of the whole topic. $P(n)$ is not a number. It is a sentence about $n$ that is either true or false once you pick an $n$.

Examples of what $P(n)$ can be:

• $P(n)$: "$n$ is a product of primes." Then $P(6)$ is true ($6=2\times 3$), $P(7)$ is true ($7$ is prime).
• $P(n)$: "$a_n=2n-1$." Then $P(3)$ is the claim "$a_3=5$."

4. The arrows of logic: $\Rightarrow$, $⟺$, $\forall$

These little symbols are the grammar the proof is written in.

5. The symbols $ab$ and $a_n$ — two different jobs for lowercase letters

Watch out: lowercase letters do two different things in the parent note.

(a) $ab$ means multiplication. When you see $n=ab$, it means $n$ equals $a$ times $b$ (the multiplication sign is invisible). Picture: a rectangle with side lengths $a$ and $b$ whose area is $n$.

(b) $a_n$ (with a subscript) means "the $n$-th term of a sequence." The little $n$ hanging below is an address, not a multiplier.

6. The symbol $■$ — "proof finished"

7. Prime and composite — the vocabulary of Example 1

The parent's flagship example (Prime Factorisation) needs two words:

Prerequisite map

Each foundation on the left must be solid before the arrow reaching Strong induction makes sense. If any box is fuzzy, reread its section above.

Where these feed back into the topic

For the big picture that ties these together, keep Sequences & Series and Mathematical Induction (ordinary) open — the Well-Ordering Principle gives yet another lens on the same idea.

Equipment checklist

Read each question, answer out loud, then reveal: