The Principle of Mathematical Induction

To prove that a predicate $P(n)$ is true for all $n\geq n_0$:

Base Case. Prove that the predicate $P(n)$ holds for a particular value $n_0$.

Induction Hypothesis. Suppose that $P(n)$ holds for some fixed value $n\geq n_0$.

Induction Step. Prove that if the induction hypothesis is true then $P(n+1)$ holds as well.

Example. Prove that for any $n\geq 1$, \begin{align*}\sum_{i=0}^{n-1}2^i&=1+2+2^2+2^3+\cdots+2^{n-1}\\&=2^n-1\end{align*}

Proof. $P(n)$: $\sum_{i=1}^{n-1}2^i=2^n-1$.

Base Case. $P(1)$: $n_0=$. $\sum_{i=0}^02^i=2^1-1$. $P(1)$ is true since the LHS=the RHS=1.

Induction Hypothesis. Suppose that $P(n)$ is true for a fixed $n\geq 1$ that is, $$\sum_{i=1}^{n-1}2^i=2^n-1$$

Induction Step. Show that $P(n+1)$ is true. \begin{align*}\sum_{i=1}^n2^i&=\sum_{i=1}^{n-1}2^i+2^n\\&=2^n-1+2^n\\&=2\cdot 2^n-1\\&=2^{n+1}-1\end{align*} Therefore $P(n+1)$ is true.

Example. Prove that for any $n\geq 1$, $$\sum_{i=1}^ni=\frac{n(n+1)}{2}$$

Proof. $P(n):=\sum_{i=1}^ni=\frac{n(n+1)}{2}$$

Base Case. $n_0=1$. $P(1)=\sum_{i=1}^1i=\frac{1(1+1)}{2}$ is true.

Induction Hypothesis. Suppose that $P(n)$ is true for some fixed $n\geq 1$.

Induction Step. Show that $P(n+1)$ is true. \begin{align*}\sum_{i=1}^{n+1}i&=\sum_{i=1}^ni+n+1\\&=\frac{n(n+1)}{2}+n+1\\&=\frac{(n+1)(n+2)}{2}\end{align*} Therefore $P(n+1)$ is true.

Example. Prove that for any $n\geq 1$, $$\prod_{i=1}^n\left(1+\frac{1}{i}\right)=\left(1+\frac{1}{1}\right)\cdot\left(1+\frac{1}{2}\right)\cdots\left(1+\frac{1}{n}\right)=n+1$$

Proof. $P(n)$: $\prod_{i=1}^n\left(1+\frac{1}{i}\right)=n+1$.

Base Case. $n_0=1$. $P(1)$: $\prod_{i=1}^1\left(1+\frac{1}{i}\right)=1+1$ is true.

Induction Hypothesis. Suppose that $P(n)$ is true for some fixed $n\geq 1$.

Induction Step. Show that $P(n+1)$ is true. \begin{align*}\prod_{i=1}^{n+1}\left(1+\frac{1}{i}\right)&=\prod_{i=1}^n\left(1+\frac{1}{i}\right)\cdot\left(1+\frac{1}{n+1}\right)\\&=(n+1)\cdot\left(1+\frac{1}{n+1}\right)\\&=n+1+1=n+2\end{align*} Therefore $P(n+1)$ is true as well.

In computer science, 0 and 1 are called the two bits. A sequence of bits, such as 100001001, is called a binary string, bit string or string of bits. For example, 10001001 is a bit string of length 8. The compliment of a bit string is the result of replacing all the 0s by 1s and vice versa. For example, the compliment of 10001001 is 01110110. The concatenation of two bit strings is the result of writing one after another. For example, the concatenation of 10001001 and 111 is 10001001111.

Let us define a sequence of bit strings as follows: \begin{align*}T_0&=0\ \mbox{and for any}\ n\geq 0\\T_{n+1}&=\mbox{the concatenation of}\ T_n\ \mbox{and the compliment of}\ T_n\end{align*}

This is an example if an inductive definition or a recursive definition. The resulting sequence is called Thue sequence named after a Norwegian mathematician Axel Thue. The first few terms of the Thue sequence are: \begin{align*}T_0&=0\\T_1&=01\\T_2&=0110\\T_3&=01101001\\T_4&=0110100110010110\end{align*}

Example. Prove that for any $n\geq 0$, the length of $T_n$ is $2^n$.

Proof. We prove this by induction.

Base Case. $T_0$ has length $1=2^0$.

Induction Hypothesis. Assume that $T_n$ has length $2^n$ for some fixed $n\geq 0$.

Induction Step. $T_{n+1}$ is the result of concatenating $T_n$ with its compliment, so its length is $$2^n+2^n=2\cdot2^n=2^{n+1}$$

Example. Prove that for every $n\geq 1$, $T_n$ begins with 01, and ends with 01 if $n$ is odd or with 10 if $n$ is even.

Proof. Base Case. $T_1=01$ so the statement is true.

Induction Hypothesis. Suppose that for some fixed $n\geq 1$, $T_n$ ends with 01 if $n$ is odd or 10 if $n$ is even.

Induction Step. $T_{n+1}$ ends with the compliment of the last two bits of $T_n$. $n+1$ is even if $n$ is odd and it is odd if $n$ is even. So $T_{n+1}$ ends with 01 if $n+1$ is odd or 10 if $n+1$ is even.

Example. Prove that for every $n\geq 0$, $T_n$ never has more than two 0s or two 1s in a row.

Proof. $T_0$ has only one bit, so the statement is true for $T_0$. We prove the statement by induction starting from $n_0=1$.

Base Case. $T_1=01$ has no more than two identical bits in a row.

Induction Hypothesis. Assume that $T_n$ has no more than two 0s or two 1s in a row.

Induction Step. $T_{n+1}$ includes $T_n$ in the first half and its compliment in the second half. By induction hypothesis, neither has more than two 0s nor two 1s in a row. Due to the statement in the previous example, the four bits at the junction can be either 0110 (if $n$ is odd) or 1010 (if $n$ is even). Neither of them contains more than two 0s or two 1s in a row. This completes the proof.

Mathematical induction also can be used to prove the Pigeonhole Principle.

Example. Prove that if $f:X\longrightarrow Y$ and $|X|>|Y|$, then there exists $x_1, x_2\in X$ with $x_1\ne x_2$ such that $f(x_1)=f(x_2)$.

Proof. We prove the statement by induction on the size of the set $X$. Let $f: X\longrightarrow Y$ be a function and $|X|>|Y|$.

Base Case. $n_0=2$. If $|X|=2$ and $|X|>|Y|$, then $|Y|=1$ and the two elements in $X$ map to the unique element of $Y$.

Induction Hypothesis. Let $|X|=n$ for some fixed $n\geq 2$ and assume that the statement is true i.e., there exist $x_,x_2\in X$ with $x_1\ne x_2$ such that $f(x_1)=f(x_2)$.

Induction Step. Let $|X|=n+1$. Pick an element $x\in X$. If there exists $x’\in X$ with $x’\ne x$ such that $f(x)=f(x’)$, then we are done. Suppose not. Then $f: X\setminus\{x\}\longrightarrow Y\setminus\{f(x)\}$, $|X\setminus\{x\}|=n$ and $|X\setminus\{x\}|>|Y\setminus\{f(x)\}|$. By induction hypothesis, there exist $x_1,x_2\in X\setminus\{x\}$ with $x_1\ne x_2$ such that $f(x_1)=f(x_2)$. This completes the proof.

References.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019