Induction

Here is one of the most important ideas in logic (and, obviously, computer science).

Induction is a powerful method for showing a property is true for all nonnegative integers.

The common analogy for inductive method is this: if we climb the first step of the ladder, we can climb the next step, and the next step, and therefore climb the entire ladder.

Let's see how it goes with another example. Say, we have 5 books on our bookshelf:

       .--.           
   .---|__|           
.--|===|--|_          
|  |===|  |'\     .---.
|  |   |  |.'\    |===|
|  |   |  |\.'\   |   |
|  |   |  | \  \  |===|
|  |   |__|  \.'\ |   |
|  |===|--|   \.'\|===|
^--^---'--^    `-'`---^
 0   1   2      3    4

ASCII art from https://www.asciiart.eu/books/books

Looking at the books from left to right, we state two rules for ourselves:

1. We are going to read the first book.
2. If a book is read, then we are going to read the following book.

We start by reading book 0. We know that if we read 0, we are going to read the following one, book 1.
If we read book 1, we know that we are going to read the following one, book 2.
If we read book 2, we know that we are going to read the following one, book 3.
...

So, we know that if book $n$ is read, then book $n + 1$ is going to be read.
We can conclude that every book on this bookshelf is going to be read. And, that's the idea of induction.

It's similar to the domino effect. The first domino falls, and the others follow.

Putting it in formal logic:

$\underline{P(0), \forall n \in \mathbb{N}. \ P(n) \implies P(n + 1)}$
$\quad \quad \quad \quad \forall m \in \mathbb{N}. \ P(m)$

In our example, $P(0)$, having read the book 0, is the basis step, or the base case.
$P(n)$ is the induction hypothesis.
The proposition $P(n) \implies P(n + 1)$ is the inductive step.

In a proof, we first need to show that the base case holds. Then, we have to assume $P(n)$ is true, then go on to show that $P(n + 1)$ holds.

Why do we assume $P(n)?$

Remember that in an implication, the only specific case we need to look at is the case where the antecedent, the "if part", is true, because the only case where the whole implication is false is when T $\implies$ F.
So, if we show that the consequent is true while the antecedent is also true, we show that the implication holds for all cases.

Let's try an example.
We can prove the summation formula with induction.

Remember that the sum of $n$ numbers is $\frac{n(n + 1)}{2}$:

Or, to put it more precisely:

What we've seen was ordinary induction. There is another kind of induction called strong induction. The difference is that strong induction just lets you make more assumptions.

In an ordinary induction argument, you assume that $P(n)$ is true and try to prove that $P(n + 1)$ is also true. In a strong induction argument, you may assume that $P(0), P(1), \ ...,$ and $P(n)$ are all true when you go to prove $P(n + 1)$.

• previous
• next