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

Extensions

The format of our induction proof can be extended to more concepts in discrete mathematics, with structural induction. Here, we identify some property is satisfied by the base elements of the set, then show that the property is preserved as we recursively construct it (i.e., a graph or tree). This property is called an invariant.

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.

There are several variations of induction, including:

• Loop invariant
• Substitution method

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