Mathematical Induction (aka Proof by Induction)

What are Proofs and What are they Good for?

Mathematical proofs are statements, either written in informal words (called informal proofs) or in a language of symbols (called formal proofs), that prove certain theorems or conjectures. They are the way in which we can be certain that our idea is valid for all possible situations and not just the current one.

While one of the main purposes of a Proof is to state, unequivocally, that a certain solution to a problem or that a certain insight into the nature of certain patterns is true, it is not, in my opinion, the most important reason to study and work on Proofs.

It is the insight gained into the particular problem, or even in the problem's field, that is the real boon when you tries to prove a certain theorem. Proofs force you to approach the problem from a different angle, not just solving this particular incarnation but in trying to come up with a unifying formula for all possible permutations. Doing so, even if you are unsuccessful, will not only give you a deeper understanding of the problem at hand, but may also lead to deeper knowledge of other fields of mathematics.

Proofs have also found their way into the functional programming paradigm, read this entry for more details.

Proofs by Induction

So the first type of proofs we'll be talking about is Proofs by Induction, also known as Mathematical Induction. It is a method where you prove that your hypothesis is true for the first case (called the base case), then for any random case (induction hypothesis), then for that particular random case +1.

Let's do a quick demonstration:


Theorem 1: The sum of the first \( n \) odd numbers is \( n^2 \)

\[ \begin{array}{lrrr} n = 2 |& 1 + 3 = 4 & \mbox{and}&n^2 = 4 \\ n = 3 |& 1 + 3 + 5 = 9 & \mbox{and}&n^2 = 9 \\ n = 4 |& 1 + 3 + 5 + 7 = 16 & \mbox{and}&n^2 = 16 \end {array}\]

Base Case, when \(n = 1\):

\(1^2 = 1\)

So our theory holds true if \(n = 1\). Now for the next step.

Induction Hypothesis, when \(n = 5 \):

\(\begin{align} &1 + 3 + 5 + 7 + 9 &=& 25 \\ &5^2 &=& 25 \end{align}\)

It also holds if \(n = 5 \)... however how can we prove that it will hold true for all other values without manually checking? Mathematical Induction states that if we can prove that \(n + 1\) is equal to \(n^2\), then our hypothesis is correct.

\(\begin{align} &\mbox{when }n + 1 = 6: \\ &1 + 3 + 5 + 7 + 9 + 11 &=& 36 \\ &6^2 &=& 36 \end{align}\)

So this proves our theory that you can find the sum of the first \(n \ \mbox{odd}\) numbers with the formula \(n^2\).

How about another example?


Theorem 2: The sum of the first \(n\) numbers can be computed with \(\frac {n\left(n+1\right)} 2\)

Base Case, when \(n = 1\):

\[\begin{array}{rcl} 1& =& \frac {n\left(n+1\right)} {\scriptsize2} \\ & =& \frac {n\left(1+1\right)} {\scriptsize2} \\ & =& \frac {1\left(2\right)} {\scriptsize2} \\ 1& =& 1 \end{array}\]

Induction Hypothesis, when \(n = 3\):

\[\begin{array}{rcl} 1 + 2 + 3& =& \frac {n\left(n+1\right)} {\scriptsize2} \\ & =& \frac {3\left(3+1\right)} {\scriptsize2} \\ & =& \frac {9+3} {\scriptsize2} \\ 6& =& 6 \end{array}\]

Now to see if \(n + 1\) holds...

According to our theory, \(1 + 2 + 3 + 4 +...+ n \) can be simplified as \(\frac {n(n + 1)} 2\), so adding \(\left(n + 1\right)\) will look like this:

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

now if we add \(\left(n + 1\right)\) to the right side of the equation we end up with \(\frac {\left(n+1\right)\left(\left(n+1\right) + 1\right)} 2\)

So taking the simplified equation of the left side and adding \(\left(n + 1\right)\) to both sides we get:

\[\begin{array}{rcl} \frac {n\left(n + 1\right)} {\scriptsize2} + (n + 1) & = & \frac {\left(n+1\right)\left(\left(n+1\right) + 1\right)} {\scriptsize2} \\ \left(n + 1\right)\left[\frac n {\scriptsize2} + 1\right] & = & \frac {\left(n+1\right)\left(n+2\right)} {\scriptsize2} \\ n^2 + 3n + 2 & = & n^2 + 3n + 2 \end{array}\]

Let's try that out with a real number, when: \(n + 1 = 4\)

\[\begin{array}{rcl} 1 + 2 + 3 + 4& =& \frac {\left(n+1\right)\left(\left(n+1\right) + 1\right)} {\scriptsize2} \\ & =& \frac {4\left(4 + 1\right)} {\scriptsize2} \\ & =& \frac {16 + 4} {\scriptsize2} \\ 10& =& 10 \end{array}\]

As you can see, in the second example we proved the formula through the algebraic methods of factoring and combining polynomials, as well as using the theorem itself in the Proof (in the Proof we substituted \(1 + 2 + 3 + 4 + .... + n\) with \(\frac {n(n+1)} 2\) where it played a central role in proving itself); checking the hypothesis with a real number was secondary. Proofs such as these are generally seen as more rigid as they describe a general formula while proving the theorem with real numbers can be seen as validating only that particular case.

Conclusion...

Just as a knowledge of factoring and combining was necessary to validate this last Proof, so are other Proofs built on previously proved ones. This is an important reason that at least a basic understanding of Proofs and their methods is extremely beneficial.

Further reading on the importance of Proofs:

14 May 2012