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$.
  • To prove this case, we often try to re-write it in a form that looks similar to the inductive hypothesis.

There are two core types of induction. The first is weak induction (or simple induction, as above). We assume the case for $P(k)$ holds true, and our inductive step only presumes that $P(k)$ holds. We can use weak induction when there’s a simple recursive relationship, i.e., our current step only relies on the previous step.

Strong induction requires that we assume all predicates $P(1),P(2),\cdots ,P(k)$ are true. Then, our inductive step allows for a reliance on predicates preceding $P(k)$. We use strong induction to model problems where there’s a reliance on previous cases past $k$.

Addendums

There are several variations of induction, including:

• Loop invariant
• Substitution method

In loop invariants, the idea is that a key loop property (i.e., the invariant) is assumed to be true at the beginning of a loop iteration. Then, for the loop to be correct, it must be true at the end of the iteration. The idea of invariants is a powerful idea when doing induction, and can be used in place of algebraic manipulations.

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}$.