1.3: The Principle of Induction

Last updated
Save as PDF

Page ID: 49260

Wikibooks - Data Structures
Wikipedia

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The chains we can build from nodes are a demonstration of the principle of mathematical induction:

Mathematical Induction

Suppose you have some property of numbers \(P(n)\)
If you can prove that when \(P(n)\) holds that \(P(n+1)\) must also hold, then
All you need to do is prove that \(P(1)\) holds to show that \(P(n)\) holds for all natural \(n\)

For example, let the property \(P(n)\) be the statement that "you can make a chain that holds \(n\) numbers". This is a property of natural numbers, because the sentence makes sense for specific values of \(n\):

you can make a chain that holds 5 numbers
you can make a chain that holds 100 numbers
you can make a chain that holds 1,000,000 numbers

Instead of proving that we can make chains of length 5, 100, and one million, we'd rather prove the general statement \(P(n)\) instead. Step 2 above is called the Inductive Hypothesis; let's show that we can prove it:

Assume that \(P(n)\) holds. That is, that we can make a chain of \(n\) elements. Now we must show that \(P(n+1)\) holds.
Assume chain is the first node of the \(n\)-element chain. Assume i is some number that we'd like to add to the chain to make an \(n+1\) length chain.
The following code can accomplish this for us:

let bigger-chain := make-node(i, chain)

Here, we have the new number i that is now the contained value of the first link of the bigger-chain. If chain had \(n\) elements, then bigger-chain must have \(n+1\) elements.

Step 3 above is called the Base Case, let's show that we can prove it:

We must show that \(P(1)\) holds. That is, that we can make a chain of one element.
The following code can accomplish this for us:

let chain := make-node(i, null)

The principle of induction says, then, that we have proven that we can make a chain of \(n\) elements for all value of \(n\geq 1\). How is this so? Probably the best way to think of induction is that it's actually a way of creating a formula to describe an infinite number of proofs. After we prove that the statement is true for \(P(1)\), the base case, we can apply the inductive hypothesis to that fact to show that \(P(2)\) holds. Since we now know that \(P(2)\) holds, we can apply the inductive hypothesis again to show that \(P(3)\) must hold. The principle says that there is nothing to stop us from doing this repeatedly, so we should assume it holds for all cases.

Induction may sound like a strange way to prove things, but it's a very useful technique. What makes the technique so useful is that it can take a hard sounding statement like "prove \(P(n)\) holds for all \(n\geq 1\)" and break it into two smaller, easier to prove statements. Typically base cases are easy to prove because they are not general statements at all. Most of the proof work is usually in the inductive hypothesis, which can often require clever ways of reformulating the statement to "attach on" a proof of the \(n+1\) case.

You can think of the contained value of a node as a base case, while the next pointer of the node as the inductive hypothesis. Just as in mathematical induction, we can break the hard problem of storing an arbitrary number of elements into an easier problem of just storing one element and then having a mechanism to attach on further elements.