Now that you’re familiar with direct proof and proof by contradiction, it’s time to discover a powerful technique of proof by induction.

*Aside: do not confuse mathematical induction with inductive or deductive reasoning. Despite the name, mathematical induction is actually a form of deductive reasoning.*

Let’s say, we want to prove that some statement \(P\) is true for all positive integers. In other words:

\(P(1)\) is true, \(P(2)\) is true, \(P(3)\) is true… etc.

We could try and prove each one directly or by contradiction, but the infinite number of positive integers makes this task rather grueling. Proof by induction is a sort of generalization that starts with the basis:

**Basis:** Prove that \(P(1)\) is true.

Then makes one generic step that can be applied indefinitely:

**Induction step:** Prove that for all \(n\geq1\), the following statement holds: If \(P(n)\) is true, then \(P(n+1)\) is also true.

See what we did there? We’ve devised another problem to solve, and it’s seemingly the same. But if the basis is true, then proving this *inductive step* will prove the theorem.

To do this, we chose an arbitrary \(n\geq1\) and assume that \(P(n)\) is true. This assumption is called the *inductive hypothesis*. The tricky part is this: we don’t prove the hypothesis directly, but prove the \(n+1\) version of it.

This is all rather amorphous, so let’s prove a real theorem.

**Theorem 1.** For all positive integers \(n\), the following is true:

\begin{equation} \label{eq:1} 1 + 2 + 3 + … + n = \frac{n(n+1)}{2} \end{equation}

**Proof**. Start with the basis when \(n\) is \(1\). Just calculate it:

\[ 1 = \frac{1(1+1)}{2}. \]

This is correct, so, the basis is proven. Now, assume that the theorem is true for any \(n\geq1\):

\begin{equation} \label{eq:2} 1 + 2 + 3 + … + n = \frac{n(n+1)}{2} \end{equation}

In the induction step we have to prove that it’s true for \(n+1\):

\begin{equation} \label{eq:3} 1 + 2 + 3 + … + (n+1) = \frac{(n+1)(n+2)}{2} \end{equation}

Having this equation, we should just try to expand it and prove directly. Since the last member on the left side is \(n+1\), the second last must be \(n\), so:

\[ 1 + 2 + 3 + … + (n + 1) = 1 + 2 + 3 + … + n + (n+1) \]

From our assumption, we know, that

\[ 1 + 2 + 3 + … + n = \frac{n(n+1)}{2}. \]

So, let’s replace it on the right hand side:

\[ 1 + 2 + 3 + … + (n + 1) = \frac{n(n+1)}{2} + (n+1) \]

And then make that addition so that the right hand side is a single fraction:

\[ 1 + 2 + 3 + … + (n + 1) = \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \]

\[ = \frac{n(n+1) + 2(n+1)}{2} \]

\[ = \frac{(n+1)(n+2)}{2}. \]

Done, we have proven that the inductive step (\ref{eq:3}) is true.

There are two results:

- The theorem is true for \(n=1\).
- If the theorem is true for any \(n\), then it’s also true for \(n+1\).

Combining these two results we can conclude that the theorem is true for all positive integers \(n\).

I had troubles with this technique because for a long time I couldn’t for the life of me understand why is this *enough* and how is the basis *helping*?! The basis seemed redundant. We assume \(P(n)\) is true, then prove that \(P(n+1)\) is true given that \(P(n)\) is true, but so what? We didn’t prove the thing we assumed!

It clicked after I understood that we don’t have to prove \(P(n)\), we just take the concrete value from the basis and use it as \(n\). Since we have a proof of \(P(n+1)\) being true **if** \(P(n)\) is true, we conclude that if \(P(1)\) is true, then \(P(1+1)\) is true.

Well, if \(P(1+1)\) is true, then, using the same idea, \(P(1+1+1)\) is true, and so forth.

The basis was the cheat-code to kick-start the process by avoiding the need to prove the assumption \ref{eq:2}.