An Introduction to Proofs: The Structure of Induction

Posted by Jason on 1/17/18 5:50 PM

General Academic_Whiteboard Writing.jpg

Induction.  It's a mathematical concept that is no doubt familiar to any student taking an introductory proof class.  It is also a concept which can bring complex feelings---the excitement of learning a new cool proof technique, the fear of being asked to prove something "obvious", or the confusion of where to start.  

What is Induction? 

Induction is one of the most powerful techniques in discrete mathematics, especially when working with the natural numbers, 0, 1, 2, 3, ...  Basically every fact of the natural numbers is proved using induction or is based on a result which is proved using induction.  Induction is also useful to prove facts about integers, rational numbers, and many other mathematical concepts---some having little or nothing to do with numbers.  Nonetheless, it often remains a mysterious concept to students, even graduate students!

Here I will spell out the details of mathematical induction in casual terms and introduce the adventurous reader to a new type of induction, structural induction, which is commonly used in logic and computer science.

Let's start with an obvious example...

Suppose I ask you to prove (justify) that every natural number is nonnegative.  Remember the natural numbers are 0, 1, 2, 3, …   More formally, we want to prove that 0 <= n for all natural numbers n.

Your first response would be: That is obvious!

And you are correct.  A teacher will likely not ever ask you to prove this, but humor me anyway.  Why is it true?  Ok, so you give it a shot.

Clearly 0 <= 0 since 0 equals itself and every other natural number is greater than 0.

Ok, that is a good start.  However, let's flesh out the statement that every other natural number is greater than 0.  Well…

First, 0 <= 0 since 0 equals itself.  Then 0 < 1, and 1 < 2 (so 0 <= 1 < 2), and 2 < 3 (so 0 <= 2 < 3), and so on.

Now we are getting at the essence of the natural numbers.  While there are many definitions of a natural number, the main idea is that there is a first natural number 0, and then every natural number n has a successor n+1.  In this way, we can build up the natural numbers.  To show that some property holds of the natural numbers we first show that 0 has the property and then show that 1 has that property and then that 2 has that property, and then 3, and so on.  The key ingredient to an induction proof is to replace the vague phase "and so on" with clear logical reasoning.  How do I go from 0 to 1, from 1 to 2, from 3 to 4?  Is there a clear pattern?  A clear method of proof?  Let's take another stab at it.

First, 0 <= 0 since 0 equals itself.  Now, for any number n, if n is greater or equal to 0, then so is n+1 since 0 <= n < n+1.

This is pretty close to the final result.  However, since induction is so common and it can be so confusing to start, the mathematical community has developed a set of terminology.  First consider the property we are trying to prove.  Let us call this P(n).  In this case P(n) is "0 <= n".  The proof of P(0) is called the base case or base step since it is the starting point (or base) of the proof.  The next step is not to prove P(n) directly, but to assume that P(n) is true and then prove P(n+1) from P(n).  This step is called the induction step, and the assumption that P(n) is true is called the induction hypothesis.  Using this terminology we can write our proof naturally, yet concisely.

Proof: Let P(n) denote the property 0 <= n.  We show that P(n) holds for all natural numbers by induction on the natural number n.

Base step (n=0): Since 0 = 0, we have that 0 <= 0.

Induction step (n+1): Assume, as the induction hypothesis, that P(n) is true.  We will show that P(n+1) is true: 0 <= n+1.  By the induction hypothesis, 0 <= n.  Also n < n + 1.  Therefore, 0 <= n + 1.

By induction, P(n) holds for all natural numbers n. QED

(By the way, QED, the Latin abbreviation for "what was to be demonstrated", is the typical way to end proofs, although is often just written using a square symbol instead of the letters QED.)  

Not only have we found a starting point to prove something seemingly trivial, but we have a template to prove other results by induction which are quite tricky to prove otherwise.

Theorem: 1 + 2 + … + n = n(n+1)/2 for all natural numbers n.

Here, we follow our template.

Proof: Let P(n) denote the property 1 + 2 + … + n = n(n+1)/2.  We show that P(n) holds for all natural numbers by induction on the natural number n.

Base step (n=0): The left-hand side of P(0) is the "empty sum" where we add nothing. Hence it equals 0.  The right-hand side is 0(0+1)/2 = 0.  Since both sides are equal, P(0) is true.

Induction step (n+1): Assume, as the induction hypothesis, that P(n) is true.  We will show that P(n+1) is true: 1 + 2 + … + (n +1) <= (n+1)((n+1) + 1)/2.

1 + 2 + … + (n +1)

= (1 + 2 + … + n) + (n+1)  [regrouping]

= (n(n+1)/2) + (n+1)   [by the induction hypothesis P(n)]

= (n^2 + n + 2n + 2) / 2 [algebra]

= (n+1)((n+1) + 1)/2 [algebra]

Therefore P(n+1) holds.

By induction, P(n) holds for all natural numbers n. QED

Striping away all the details unique to each proof, we have this template.

Proof: Let P(n) denote the property [fill in the property you are trying to prove].  We show that P(n) holds for all natural numbers by induction on the natural number n.

Base step (n=0): [Give a proof of P(0).  Often this is easy and just involves checking that P(0) is true.]

Induction step (n+1): Assume, as the induction hypothesis, that P(n) is true.  We will show that P(n+1) is true: [write out P(n+1), replacing n in P(n) with n+1]

[give a proof of P(n+1) using the induction hypothesis P(n).  Clearly label where you use the induction hypothesis, by writing "induction hypothesis" or "IH"]

By induction, P(n) holds for all natural numbers n. QED

Yes, this template is a constraint on your writing, but like good constraints in poetry (e.g. Haiku) it makes your writing more (mathematically) beautiful and it helps you get started.  (Also, like poetry, experienced poets/mathematicians will bend the rules.  Nonetheless, at the beginning stage you should follow this template---or the template your teacher gave you---religiously.)

Recursion: induction's best friend

Now that we have a template, we just have to fill it in.  However, filling in the proof of the induction step can be challenging.  For example in the previous induction proof, we wanted to prove P(n+1): 1 + 2 + … + (n +1) <= (n+1)((n+1) + 1)/2.  Why did I know to break up 1 + 2 + … + (n +1) into (1 + 2 + … n) + (n+1)?

The answer is recursion.  Recursion is when we define a function f(n) on the natural numbers by first defining f(0) and then defining f(n+1) in terms of f(n).  For example,

f(0) = 0,    f(n+1) = f(n) + n + 1

What is this function f(n)?  It is exactly f(n) = 1 + 2 + … + n.  However, when we think of this function recursively, we instantly see that

1 + 2 + … + (n +1) = f(n+1) = f(n) + n + 1 = (1 + 2 + … + n) + (n + 1)

Induction and recursion are best pals, virtually inseparable.  Wherever you see induction, you will most often see recursion, and wherever you see recursion, you will use induction to prove things about it.

Consider the following two recursive definitions of common functions.  The exponential function g(n) = 2^n is defined recursively as

g(0) = 1,    g(n+1) = 2 * g(n)

whereas the factorial function h(n) = n! is defined recursively as

h(0) = 1,    h(n+1) = (n+1) * h(n)

(Have you ever wondered why 0! = 1 and not 0?  What if we started the recursion with h(0) = 0?)  

Now, back to induction.  In the induction step of an induction proof, we want to prove P(n+1) using the induction hypothesis P(n).  One should look for a way to use recursion to turn P(n+1) into a statement about P(n).  Here is a good example:

Theorem: 1 + 2 + 2^2 + … + 2^n = 2^(n+1) - 1 for all natural numbers n.

Notice that, since 2^0 = 1, the left-hand-side is recursively defined via

f(0) = 1,    f(n+1) = f(n) + 2^(n+1)

and the exponential 2^n in the right-hand side is also recursively defined as we saw above.  Now, we just follow our template and carefully exploit any recursion we see.

Proof: Let P(n) denote the property 1 + 2 + 2^2 + … + 2^n = 2^(n+1) - 1.  We show that P(n) holds for all natural numbers by induction on the natural number n.

Base step (n=0): P(0) says 1 = 2^(0+1) - 1.  This is true.

Induction step (n+1): Assume, as the induction hypothesis, that P(n) is true.  We will show that P(n+1) is true: 1 + 2 + 2^2 + … + 2^(n+1) = 2^((n+1)+1) - 1

1 + 2 + 2^2 + … + 2r^(n+1)

= (1 + 2 + 2^2 + … + 2^n) + 2^(n+1)  [regrouping] (notice the recursion here)

= (2^(n+1) - 1) + 2^(n+1)   [by the induction hypothesis P(n)]

= 2 * 2^(n+1) - 1 [algebra]

= e2^((n+1)+1) - 1 [algebra] (notice the recursion: 2^(m+1) = 2 * 2^m)

Therefore P(n+1) holds.

By induction, P(n) holds for all natural numbers n. QED

To test your knowledge, try the following exercise.

Exercise

Prove 1(1!) + 2(2!) + … + n(n!) = (n+1)! − 1 using induction.

Remember to use recursion!

A different type of induction

There is, of course, a lot more that could be said about ordinary induction.  One can start with other base cases besides 0, or with two base cases, e.g. 0 and 1.  In strong induction one uses not only P(n) as an induction hypothesis, but also P(n-1), P(n-2), …, P(0).  Then there are the many marvelous examples of things one can prove using induction.

Instead, I want to go a different direction.  I want to show a different type of induction, where one doesn't work with the natural numbers which are all in a row, but instead works with more complicated types of objects that appear in mathematics, logic, or computer science.

Other inductive definitions

As we already said, the natural numbers have two defining properties.

  • (Base) 0 is a natural number.
  • (Induction) Every natural number n as a successor n+1.

That is it.  This is the essence of the natural numbers.  Well, not exactly.  The rationals, integers, and the real numbers also have these two properties, but what is different about them is that they contain extra numbers.  If one starts at 0 and then goes to the next successor 1, and the next 2, and so on, one will never reach numbers such as -1, ⅓, or sqrt(2).  To account for this, we also require another property.

  • The natural numbers form the smallest set with these two properties.

This is the essence of the natural numbers.  However, this idea can also be used to for other types of objects in mathematics.  One of these objects is a term.  For our purposes, a term is composed of variables like x, y, and z as well the operations + and *.  For example,

(x + ((z * y) + z))

Notice, I also added parentheses, and I went overboard so that each operation has a pair of parentheses around it.  This is so that we can be explicit about what we mean by each term without having to adopt an order of operations.  Now, terms like this can be defined inductively in the same way that natural numbers are.

  • (Base) Each variable is a term.
  • (Induction) If t and s are terms, then so are (t * s) and (t + s).

Again, the set of terms is the smallest set of objects obeying these two rules.

Structural induction

Let's try to prove something about our terms.

Theorem: Given terms (using only the operations + and *) if every variable is replaced with an even number, then the result is even.

Again, you may say this is obvious.  But why?  You may say:

Addition and multiplication of even numbers preserves even-ness.

You are correct, but once again there is a hidden "and so on" in your argument.  

even + even = even

even * even = even

(even * even) + even = even + even = even

(even + even) * even = even * even = even

and so on

Once again induction can come to the rescue.  Since terms can be defined inductively with a base case and and induction case, we can follow the same induction template as with the natural numbers.

Proof: Let P(t) denote the property: if all variables in the term t are replaced with even numbers then the term t is even.  We show that P(t) holds for all terms by induction on the term t.

Base step (t is a variable): Since t is a variable x and that variable is even, then so is t.

Induction step (t = (s + r)): Assume, as the induction hypothesis, that P(s) is true and P(r) is also true.  We will show that P((s + r)) is true.  Assume every variable in (s + r) is even.  Then every variable in s and r is even (since these variables are exactly the variables in t).   By the induction hypothesis, both s and r are even.  Therefore (s + r) is even.  Therefore P((s + r)) holds.

Induction step (t = (s * r)): Assume, as the induction hypothesis, that P(s) is true and P(r) is also true.  We will show that P((s * r)) is true.  Assume every variable in (s * r) is even.  Then every variable in s and r is even (since these variables are exactly the variables in t).   By the induction hypothesis, both s and r are even.  Therefore (s * r) is even. Therefore P((s * r)) holds.

By induction, P(t) holds for all terms t. QED

While this may seem like overkill, it helps to show the structure of this kind of induction, which is called structural induction.  What is going on here?  Every term is build up from previous terms via one of the operators + or * and those terms are built up from smaller terms, etc.   That is until we get to the variables.  Hence it is enough to show that (1) our property P holds for the variables, and (2) if it holds for terms s and r, it also holds for (s + r) and (s * r).

Also, notice there are two induction cases in the above proof.  That is because there are two ways to construct a term from smaller terms.  (A more crafty proof would combine the two induction cases, since they are basically the same.  See the next example.)

Recursion: still induction's best friend

Now, let's prove something more interesting.

Theorem: For every term t, the number of operations is one less than the number of variables.

How do we go about proving this?  Just as with regular induction, we look to recursion.  We can define the number of variables v(t) in a term t recursively:

  • v(x) = 1 for any variable x
  • v(r @ s) = v(r) + v(s) where r and s are terms and @ is an operation + or *

We can also define the number of operations o(t) in a term t recursively:

  • o(x) = 0 for any variable x
  • o(r @ s) = o(r) + o(s) + 1 where r and s are terms and @ is an operation + or *

Now we are trying to prove the following for any term t:

o(t) = v(t) - 1

Here is the induction proof.

Proof: Let P(t) denote the property o(t) = v(t) - 1.  We show that P(t) holds for all terms by induction on the term t.

Base step (t is a variable): Since t is a variable x, we have o(t) = 0 and v(t) - 1 = 1 - 1 = 0.  So P(t) is true.

Induction step (t = (s @ r)): Assume, as the induction hypothesis, that P(s) is true and P(r) is also true.  We will show that P((s @ r)) is true where @ is either * or +.

o(s @ r)

= o(s) + o(r) + 1 [recursive definition of o]

= (v(s) - 1) + (v(r) - 1) + 1 [induction hypothesis]

= v(s) + v(r) - 1

= v(s @ r) - 1 [recursive definition of v]

Therefore P((s @ r)) holds.

By induction, P(t) holds for all terms t. QED

Conclusion

There you have it.  Induction and structural induction are natural and powerful methods to prove facts about natural numbers and any inductively definable structure.  Usually these proofs make heavy use of recursion.  

Inductively definable structures are quite common in logic, since one needs to work with logical formulas and logical terms.  Also, they come up often in computer science as well.

If you would like to learn more about the mathematics behind structural induction, I recommend Section 1.4 of Enderton's A Mathematical Introduction to Logic (2nd edition).

Happy Inducting!

Are you interested in connecting with a mathematics tutor like Dan?

Contact Us!

Want to read more on the topic?

Solving The “I’m Not Good At Math” Problem

How to Understand Matrix Factorization

How to Sketch Any Graph by Eye