Proof by induction

Mathematical induction is a method of proving that some statement $P(n)$ is true for every natural number $n$.

$$(P(0)\wedge \forall k\in \mathbb{N},P(k)⟹P(k+1))⟹\forall n\in \mathbb{N},P(n)$$

If we prove a statement for a given step $k$, and the next step $k+1$, then the following steps will be true. An analogy for this is that of dominoes: if one domino falls, and the next does too, then the rest will fall.

Procedure

Simple induction has several key steps:

• Define the predicate. This allows us to figure out what it is that we’re proving.
• Determine whether the base case is true, $P(0)$. If it is true, we proceed.
• We assume the case is true for $P(k)$, where $k\in \mathbb{N}$ is some arbitrary natural number. This is called the induction hypothesis.
• We then attempt to prove the case $P(k+1)$. If this case is proven, then by the principle of mathematical induction, the statement is true for all $n\ge 0$.

Example

Prove $(\text{cis}\theta {)}^n=\text{cis}n\theta$, De Moivre’s theorem, for $n\ge 0$, where $n\in \mathbb{N}$.

We first let $n=0$:

$$(\text{cis}\theta {)}^0=\text{cis}(0\cdot \theta )$$ $$1=\cos 0+i\sin 0$$ $$1=1$$

So we’ve proven the statement is true for $P(0)$.

We then let $n=k$, where $k\in \mathbb{N}$, and assume the statement is true for $P(k)$. We assume:

$$(\text{cis}\theta {)}^k=\text{cis}(k\theta )$$

We then attempt to prove the statement for $n=k+1$.

$$(\text{cis}\theta {)}^{k+1}=\text{cis}((k+1)\theta )$$

After some fairly boring manipulations, we arrive at the conclusion that the left-hand side will equal the right hand side. Where the case $P(k)$ appears in our manipulations, we bring it down and use it to help our simplification and manipulations.

As the left-hand side is equal to the right-hand side, and it was shown that $P(0)$, the base case, is true, and it was proven that $n=k$ and $n=k+1$ is true, thus the open statement above has been proven to be true for $n\in \mathbb{N}$.