2.5a Simple Induction

Simple (Weak) Induction

Simple induction is a logical argument that establishes the truth of a given propositional function $P(n)$ for an infinite set of numbers by reasoning about it by finite means. It consists of:

1. Proving that the statement holds for a lower limit value $n_0$, usually 0 or 1, known as the base case.
2. Assuming that the statement holds for some $k\ge n_0$, known as the inductive hypothesis.
3. Proving that since the statement $P(k)$ is assumed to hold, it also holds for $k+1$, known as the inductive step.

As a logical implication, this can be described as
$(n_0,k\in \mathbb{N})(k\ge n_0)(P(n_0)\wedge (P(k)⟹P(k+1))).$

Simple vs. Strong Induction $P(k)$ holds for some number $k\ge n_0$. It does not assume that the proposition holds for all natural numbers $n_0,n_0+1,\dots ,k$. The latter is the inductive hypothesis of strong induction (2.5b).

Simple induction only assumes that

Intuition

Suppose we have a line of $n$ dominoes. Then, if we knock the $k$-th domino, the $(k+1)$-th domino will be knocked too. This is essentially what simple induction represents; we only have to prove that if we assume our proposition $P(k)$, then $P(k+1)$ is true. The base case is simply an easy test of whether we should even use our time to prove for $P(k+1)$. We will see in 2.5b that strong induction is a little bit more elaborate than simply $P(k)⟹P(k+1)$.

It is also important that we choose a right statement to prove, since not all statements are strong enough to be proven. Check the last example on this page to see this in action.

Examples

(Gauss Summation) Proving that $\forall n\in \mathbb{N},{\sum }_{i=0}^{n}i=\frac{n(n+1)}{2}$

We proceed by induction on $n$:

• Base case: $(n=0)$: Since ${\sum }_{i=0}^{0}i=\frac{0(0+1)}{2}=0$, our base case holds.
• Inductive hypothesis: We assume that our statement holds for some arbitrary $n=k\ge 0$.
• Inductive step: Since our statement ${\sum }_{i=0}^{k}i=\frac{k(k+1)}{2}$ holds for $k$, it holds for $k+1$ such that
  ${\sum }_{i=0}^{k+1}i=\left({\sum }_{i=0}^{k}i\right)+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}.$

By the principles of mathematical induction, the claim holds for $k+1$, and therefore it holds for all natural numbers $n\in \mathbb{N}$.

Proving that $\forall n\in \mathbb{N},3\mid n^3-n$

We proceed by induction on $n$. Since $3\mid 0$, it holds. We then assume that $3\mid k^3-k$ for some $k\ge 0$, such that $k^3-k=3q_1$ for some $q$. Our inductive step needs to prove that $3\mid (k+1{)}^3-(k+1)$:

$$\begin{array}{rl}(k+1{)}^3-(k+1)& =k^3+3k^2+3k+1-(k+1)\\ & =(k^3-k)+3(k^2+3k)\\ & =3q+3(k^2+k)\\ & =3(k^2+k+q).\end{array}$$

As such, we have proved that $3\mid n^3-n$ for all natural numbers $n\in \mathbb{N}$.

(Two-Color Theorem) Any box with $n$ lines can be colored using 2 colors such that any two adjacent shapes have different colors.

The following drawing shows that the two-color theorem holds for $n=2$:

\begin{document}
\begin{tikzpicture}
 
% Box
\draw[very thick] (0, 0) -- (5, 0) -- (5, -3) -- (0, -3) -- cycle;
 
% Lines
\draw[very thick] (3, -3) -- (0, 0);
\draw[very thick] (0, -1.5) -- (5, -1.5);
 
% Fills
\draw[thin, fill=red, opacity=0.25] (1.5, -1.5) -- (0, 0) -- (0, -1.5) -- (5, -1.5) -- (5, -3) -- (3, -3) -- cycle;
\draw[thin, fill=blue, opacity=0.25] (5, -1.5) -- (5, 0) -- (0, 0) -- (3, -3) -- (0, -3) -- (0, -1.5) -- cycle;
 
\end{tikzpicture}
\end{document}

Now that we have a clear picture of the idea, we can proceed by induction on $n$:

• Base case: The theorem surely holds for $n=0$ since it can even be colored using 1 color.
• Inductive hypothesis: We assume that the theorem holds for some $k\ge 0$.
• Inductive step:

For all $n\ge 1$, the sum of the first $n$ odd numbers is a perfect square

We proceed by induction on $n$:

• Base case: the first odd number is $n=1$, which is a perfect square.
• Hypothesis: Assume that the sum of the first $k$ odd numbers form a perfect square, $m^2$.
• Step: We have that the sum of the first $k+1$ odd numbers is $m^2+k+1$.

…But now what? This doesn’t help us at all! It turns out that our statement is too weak to be proven, since it does not have enough structure to make it meaningful.

Let’s now do a check on our statement and see the first few base cases:

• $n=1$: $1=1^2$
• $n=2$: $1+3=2^2$
• $n=3$: $1+3+5=3^2$
• $n=4$: $1+3+5+7=4^2$

It turns out that not only does our statement hold for the base cases, but the sum of the first $n$ odd numbers is exactly $n^2$! As such, we can continue with our proof:

• Hypothesis: The sum of the first $k$ odd numbers is $k^2$.
• Step: The $(k+1)$-st odd number is $2k+1$. As such, the sum of the first $k+1$ odd numbers is $k^2+2k+1=(k+1{)}^2$. Therefore, the theorem holds.