Principle of Mathematical Induction

What is Induction?

Mathematical induction is a type of proof that is carried out in two steps:

1. Base Case - prove the statement for the smallest case. For example, if you are trying to prove a statement for all natural numbers, the base case will be $n=1$.
2. Inductive Step - assume the statement works for $n=k$, and prove that it works for $n=k+1$.

This should make sense intuitively. First, prove that it works for the smallest case. Then, prove that it works for the next case. This means it works for all cases.

Domino Analogy

Induction is often compared to the domino effect.

1. Base case - The first domino falls.
2. Inductive step - If any domino falls, then its next neighbor also falls .

Example

Prove the formula $$1+2+...+n=\frac{n(n+1)}{2}$$ holds true for every positive integer $n$.

Base case: When $n=1$, the formula yields $1=\frac{1(2)}{2}$, which is true.

Inductive step: Assume a typical case $n=k$ and show that the next case $k+1$ follows. In other words, we assume $$1+2+...+k=\frac{k(k+1)}{2}$$ and want to show $$1+2+...+k+(k+1)=\frac{(k+1)(k+2)}{2}.$$

We could derive this through algebraic manipulation: \begin{align} 1+2+ ... +k+(k+1)&=\frac{k(k+1)}{2} + (k+1) \
&=\frac{k(k+1)+2(k+1)}{2} \
&=\frac{(k+1)(k+2)}{2} ;;. \
\end{align}

We have shown that the formula holds in the case $n=1$ and each case follows from the previous case. By induction, the formula holds for all positive integers. $\square$