Induction

We write $P(n)$ to mean that $n$ has property $P$. For instance, if $E(n)$ means that $n$ is an even number, then $E(4)$ is true but $E(5)$ is false.

Suppose that you want to prove all natural numbers greater than or equal to $m$ have some property $P$. That is, you want to prove that $P(n)$ is true for all $n\ge m\ge 0$. To prove this by induction, you must prove the following two statements:

Base case: $P(m)$ is true.
Induction step: For all $k\ge m$, if $P(k)$ is true, then $P(k+1)$ is true.

After proving the above two statements, you can conclude "Therefore, $P(n)$ is true for all $n\ge m$ by induction.

Note

Statement 2 is a conditional. To prove this statement, consider an arbitrary $k\ge m$ and assume that $P(k)$ is true. Then, you must verify that $P(k+1)$ is true. The statement $P(k)$ is called the induction hypothesis.

Claim 1. For all $n\ge 1$, $\sum_{i=1}^n (2i-1)=n^2$.

Proof. The proof is by induction.

Base case: The base case is $n=1$. We have that

\[ \sum_{i=1}^1 (2i-1)= 2*1-1 - 1 = 1^2. \]

The induction hypothesis is $\sum_{i=1}^k (2i-1)=k^2$. We must show that $\sum_{i=1}^{k+1} (2i-1)=(k+1)^2$. This is proved as follows:

\[ \begin{align} \sum_{i=1}^{k+1} (2i-1) & = & \sum_{i=1}^{k} (2i-1) + (2(k+1)-1)\\ & = & k^2 + 2k + 2 - 1\\ & = & k^2 + 2k + 1\\ & = & (k+1)^2 \end{align} \]

Therefore, by induction for all $n\ge 1$, $\sum_{i=1}^n (2i-1)=n^2$. QED

Strong Induction

To prove that for all $n\ge m\ge 0$, $P(n)$ by strong induction, you must prove the following two statements:

Base case: $P(m)$ is true.
Induction step: Assume that $P(k)$ is true for all $k < n$. Prove that $P(n)$ is true.

Claim 2. Any positive integer $n$ can be expressed uniquely as a product of prime numbers.

Proof. The proof using strong induction on $n$. The base case is $n=1$. Clearly, $1$ can be expressed as an empty product of prime numbers. Suppose that for any $1< k< n$, $k$ can be written as a product of primes. We must show that $n$ can be written as a product of primes. There are two cases: 1. $n$ is prime or 2. $n$ is not prime. If $n$ is prime, then $n$ can be expressed as the product of 1 prime number (namely $n$ itself). If $n$ is not prime, then $n=ab$ where $a\ge 2 and $b\ge 2$. Since $a< n$ and $b< n$, by the induction hypothesis, both $a$ and $b$ can be written as a product of primes. Then, $n=ab$ can also be written as a product of primes. QED

Weak and Strong Induction

Note that the above proof used strong induction rather than weak induction. We did not argue that if $k$ is the product of primes, then so is $k+1$. When we noted that $n=ab$ in the above proof, all we can conclude is that $a< n$ and $b< n$. We then apply strong induction.

See this discussion for further discussion of weak and strong induction.

Inductive Definitions and Structural Induction

Consider the following definition:

Nice Terms

The set of nice terms is inductively defined as follows:

Any letter $\mathrm{a}$, $\mathrm{b}$, $\mathrm{c}$, $\mathrm{d}$ is a nice term.
If $s$ and $s'$ are nice terms, then so is $[s \circ s']$.
Nothing else is a nice term.

Examples of nice terms.

The following are examples of nice terms include:

$\mathrm{a}$,
$[\mathrm{a}\circ \mathrm{a}]$,
$[[\mathrm{a}\circ \mathrm{b}]\circ [\mathrm{c}\circ\mathrm{d}]]$,
$[[\mathrm{a}\circ \mathrm{a}]\circ[\mathrm{b}\circ[\mathrm{c}\circ[\mathrm{d}\circ\mathrm{a}]]]]$.

The length of a nice term is the number characters in the term. Note that we have the following

The length of $\mathrm{a}$ is 1 and there are 0 occurrences of $[$,
The length of $[\mathrm{a}\circ \mathrm{a}]$ is 5 and there is 1 occurrence of $[$,
The length of $[[\mathrm{a}\circ \mathrm{b}]\circ [\mathrm{c}\circ\mathrm{d}]]$ is 13 and there is 3 occurrences of $[$,
The length of $[[\mathrm{a}\circ \mathrm{a}]\circ[\mathrm{b}\circ[\mathrm{c}\circ[\mathrm{d}\circ\mathrm{a}]]]]$ is 21 and there are 5 occurrences of $[$.

Notice that in each case, the number of occurrences of $[$ in a nice term is strictly less than $n/2$ where $n$ the length of the term. This is not necessarily true if an expression is not a nice term:

The length of $[[[[a\circ b$ is 6, but there are $4>6/2$ occurrences of $[$.

Claim 3. For any $n$, the number of $[$ in a nice term of length $n$ is $< n/2$.

Proof. We prove the statement by strong induction on the length of a nice term. A term of length 1 has 0 occurrences of the symbol '$[$', so the statement holds for $n=1$. We must show the following conditional claim is true:

If for every $k < n$, any nice term of length $k$ has $k/2$ $[$'s, then any nice term of length $n$ has $n/2$ $[$'s.

To show this conditional, assume that for any $k< n$, nice terms of length $k$ contain less than $k/2$ occurrences of $[$. This assumption is called the inductive hypothesis. We want to show the same is true for nice terms of length $n$.

So suppose $t$ is a nice term of length $n$. Because nice terms are inductively defined, we have two cases: (1) $t$ is a letter by itself, or $t$ is $[s \circ s']$ for some nice terms $s$ and~$s'$.

$t$ is a letter. Then $n = 1$, and the number of $[$ in $t$ is $0$. Since $0 < 1/2$, the claim holds.
$t$ is $[s \circ s']$ for some nice terms $s$ and~$s'$. Let $k$ be the length of $s$ and $k'$ be the length of $s'$. Then the length $n$ of $t$ is $k+k'+3$ (the lengths of $s$ and $s'$ plus three symbols $[$, $\circ$, $]$). Since $k+k'+3$ is always greater than $k$, $k < n$. Similarly, $k' < n$. That means that the induction hypothesis applies to the terms $s$ and $s'$. Let $m$ be the number of $[$ in $s$ and $m'$ the number of $[$ in $s'$. By the induction hypothis applied to $s$ and $s'$, we have that $m< k/2$ and $m' < k'/2$.

Now, the number of $[$ in $t$ is the number of $[$ in $s$, plus the number of $[$ in $s'$, plus $1$, i.e., it is $m + m' + 1$. Since $m < k/2$ and $m' < k'/2$ we have:

\[ m + m' + 1 < \frac{k}{2} + \frac{k'}{2} + 1 = \frac{k+k'+2}{2} < \frac{k+k'+3}{2} = n/2. \]

In each case, we have shown that the number of $[$ in $t$ is less than $n/2$ (on the basis of the inductive hypothesis). By strong induction, the claim follows. QED

Additional Reading

Chapter 5 of Open Logic Initiative Notes on Sets, Functions and Relations.
Chapter 4 of Joel David Hamkins, Proof and the Art of Mathematics, The MIT Press, 2020.

Exercises

Prove that for all $n\ge 0$, $\sum_{i=0}^n 2^i = 2^{n+1} - 1$.

Show Answer
The proof is by induction on $n$.

Base Case: When $n=0$, we have $\sum_{i=0}^0 2^i = 2^0=1 = 2^{0+1} - 1$.

Let $k\ge 0$. The induction hypothesis is $\sum_{i=0}^k 2^i = 2^{k+1} - 1$.

We must show that $\sum_{i=0}^{k+1} 2^i = 2^{(k+1)+1} - 1$. This is proved as follows:

\[ \begin{align} \sum_{i=0}^{k+1} 2^i & = & \sum_{i=0}^{k} 2^i + 2^{k+1}\\ & = & 2^{k+1} - 1 + 2^{k+1}\\ & = & 2\times 2^{k+1} - 1\\ & = & 2^{(k+1)+1} - 1. \end{align} \]

Note that the second equality follows by the induction hypothesis. Therefore, by induction for all $n\ge 0$, $\sum_{i=0}^n 2^i = 2^{n+1} - 1$. QED
Prove that for all integers $n\ge 5$, $n^2<2^n$.

Show Answer
Proof. The proof is by induction on $n$.

Base Case: When $n=5$, we have $5^2 = 25 < 32 = 2^5$.

Induction Hypothesis: If $k\ge 5$, then $k^2 < 2^k$.

Induction Step: We must show that if $k\ge 5$, then $(k+1)^2 < 2^{k+1}$. Suppose that $k\ge 5$. Then, $k^2\ge 5k$. First, note that:

\[ \begin{align} (k+1)^2 & = & k^2 + 2k + 1 \\ & < & k^2 + 2k + 5\\ & \le & k^2 + 2k + k\\ & = & k^2 + 3k\\ & < & k^2 + 5k\\ & \le & k^2 + k^2\\ & = & 2k^2 \end{align} \]

Then, we have that:

\[ \begin{align} (k+1)^2 & < & 2k^2 \\ & < & 2*2^k\\ & = & 2^{k+1} \end{align} \]

The second inequality follows from the induction hypothesis. Therefore, by induction for all integers $n\ge 5$, $n^2<2^n$. QED
What is wrong with the following proof by induction that for all $n\ge 0$, $n+3=n+7$?
Proof. Let $P(n)$ be the statement $n+3=n+7$. We will prove that this is true for all $n\in\mathbb{N}$. Assume by induction that $P(k)$ is true. That is, $k+3=k+7$. We must show that $P(k+1)$ is true. Now, since $k+3=k+7$, adding 1 to both sides gives us $k+3+1 = k+7+1$, so $(k+1)+3 = (k+1)+7$. Hence, $P(k+1)$ is true. So, by induction $P(n)$ is true for all $n\in\mathbb{N}$.

Show Answer
The base case was not verified. Indeed, the base case does not hold: $0+3 \neq 0+7$.
What is wrong with the following proof by induction that for all $n\ge 0$, $n<100$?
Proof. Let $P(n)$ be the statement $n<100$. We will prove that this is true for all $n\in\mathbb{N}$. The base case is $0<100$ which is true. The induction step is to show that $P(k)$ is true implies that $P(k+1)$ is true. Assume that $P(k)$ is true. That is, $k<100$. So, $k$ is some number like $80$. Clearly, $k+1<100$ (for instance, $80+1 =81<100$), so $P(k+1)$ is true. So, by induction $P(n)$ is true for all $n\in\mathbb{N}$.

Show Answer
The proof of the induction step is not correct. You must show that for all $k$, if $k<100$, then $k+1 < 100$. While this is true for $k=80$, it is not true when $k$ is, for example, $99$.