Proof by Induction Example

Proof by induction is a powerful, accepted tool for producing not only mathematical proofs but also proofs of algorithms in computer science and other fields as well.

The concept of proof by induction, is generally described as being a three step process:

1. Prove a base case (in many cases we call this \(P(1)\)).
2. Assume that the \(k\)th case is true (we call this \(P(k)\)).
3. Show that the \(k+1\)th case is true (we call this \(P(k+1)\)).

As can be seen \(P(1) \rightarrow P(2)\), since our base case has been established at \( P(1)\) and we have shown that for our \( k+1\)th case, when \( k = 1\) (i.e. \(P(2)\)) our proposition stands. This can be further extended to show that \( P(2) \rightarrow P(3) \rightarrow ... \rightarrow P(n)\).

So, in less-mathematical terms, proof by induction is as simple as proving some proposition is true for some starting value, and then verifying that it is true for the next one, and the next one, continuing on as far as it needs to or, in other words, to the \(n\)th value.

The following is a simple, somewhat standard example.

Problem

\( \forall n \in \mathbb{N} \), prove that: \[ \sum_{i = 1}^{n} i = \frac{n \left( n + 1 \right)}{2} \]

(This is saying that if we sum up all the numbers from one to \(n\), that sum should equivalently be calculable by \( \frac{n \left( n + 1 \right)}{2} \))

Proof

 Before we start the proof, it's useful to...
\[
  \text{let } P(n) =  \sum_{i = 1}^{n} i
\]

Now...

Proof by Induction

Step 1: Prove base-case, \( P(1) \):

So, the sum of all number from one to one is:
\[
  P(1) = \sum_{i = 1}^{1} i = 1
\]

Now we verify that our formula works for \( n = 1\):
\[
  \frac{n \left(n + 1 \right)}{2} = \frac{1 \left(1 + 1 \right)}{2} = \frac{2}{2} = 1
\]

It checks!

Step 2: Assume that \( P(k) \) is true:

So, here we are assuming that:
\[
  P(k) = \sum_{i = 1}^{k} i = 1 + 2 + 3 + ... + k = \frac{k \left( k + 1 \right)}{2}
\]

Step 3: Show that \( P(k+1) \) is consistent:

So, \( P(k+1) \) looks like, (replacing \(n\) with \( k + 1\)):
\[
  P(k+1) =  \sum_{i = 1}^{k+1} i = 1 + 2 + 3 + ... + k + (k + 1) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}
\]

Noticing that \( 1 + 2 + 3 + ... + k \) is the same as \( P(k) \) from Step 2:
\[
  \frac{k \left( k + 1 \right)}{2} + \left( k + 1 \right) = \frac{\left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]}{2}
\]

Multiplying both sides by \(2\):
\[
   k \left( k + 1 \right) + 2\left( k + 1 \right) = \left( k + 1 \right) \left[ \left( k + 1 \right) + 1 \right]
\]

Distribute \(k\) and \(2\) on the left, add the \(1\)s on the right:
\[
  k^2 + k + 2k + 2 = \left( k + 1 \right) \left( k + 2 \right)
\]

FOIL the right:
\[
  k^2 + k + 2k + 2 = k^2 + 2k + k + 2 \text{      $\square$}
\]

It's really as easy as that!