An introduction to proofs: the structure of induction

academics math
By Jason

 

Induction.  It's a mathematical concept that is no doubt familiar to any student taking an introductory proof class.  It is also a concept that 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 built 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!

Comments

topicTopics
academics study skills MCAT medical school admissions SAT expository writing college admissions English MD/PhD admissions strategy writing LSAT GMAT GRE physics chemistry math biology graduate admissions academic advice ACT interview prep law school admissions test anxiety language learning premed MBA admissions career advice personal statements homework help AP exams creative writing MD study schedules computer science test prep Common Application summer activities history mathematics philosophy organic chemistry secondary applications economics supplements research 1L PSAT admissions coaching grammar law psychology statistics & probability legal studies ESL CARS SSAT covid-19 dental admissions logic games reading comprehension engineering USMLE calculus PhD admissions Spanish mentorship parents Latin biochemistry case coaching verbal reasoning DAT English literature STEM excel medical school political science skills AMCAS French Linguistics MBA coursework Tutoring Approaches academic integrity chinese letters of recommendation Anki DO Social Advocacy admissions advice algebra artificial intelligence astrophysics business cell biology classics diversity statement gap year genetics geometry kinematics linear algebra mechanical engineering mental health presentations quantitative reasoning study abroad technical interviews time management work and activities 2L DMD IB exams ISEE MD/PhD programs Sentence Correction adjusting to college algorithms amino acids analysis essay art history athletics business skills careers cold emails data science dental school finance first generation student functions information sessions international students internships logic networking poetry resume revising science social sciences software engineering tech industry trigonometry writer's block 3L AAMC Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian Lagrange multipliers London MD vs PhD MMI Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture argumentative writing art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser campus visits cantonese capacitors capital markets central limit theorem centrifugal force chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism escape velocity evolution executive function freewriting genomics graphing harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports linear maps mandarin chinese matrices mba medical physics meiosis microeconomics mitosis mnemonics music music theory nervous system neurology neuroscience object-oriented programming office hours operating systems