**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