Investigation strategies

Mathematical induction

Because much of the numerical reasoning in discrete mathematics is accomplished with natural numbers (1, 2, 3, . . .) the proof technique of mathematical induction is both useful and common.

Inductive proofs are based on the idea that you want to prove an infinite sequence of statements:

property p is true for number 1.
property p is true for number 2.
property p is true for number 3.
etc.

The method of proof is based on adding to the list infinitely many implications:

p is true for 1.
If p is true for 1 then p is true for 2.
p is true for 2.
If p is true for 2 then p is true for 3.
p is true for 3.
If p is true for 3 then p is true for 4.
etc.

By modus ponens, if you know

p is true for 1.

If p is true for 1 then p is true for 2.

then you can conclude

p is true for 2.

And if you know

p is true for 2.

If p is true for 2 then p is true for 3.

then you can conclude

p is true for 3.

And so on. That is, if you can prove

p is true for 1.

and all of the

If p is true for. . . then p is true for. . . .

then you've proved all of the

p is true for. . . .

statements. In other words, if you can prove

p is true for 1.

and

If p is true for n, then p is true for n + 1 for all natural numbers n.

then you've proved

p is true for n for all natural numbers n.

An example

As an example from graph theory, suppose you want to prove

In any tree, the number of vertices is one less than the number of edges.

A way to state this conjecture in terms of natural numbers is to say:

Any tree with n vertices has n – 1 edges.

Then the statement p is true for n means Any tree with n vertices has n–1 edges.

Proof: When n = 1, the tree consists of a single vertex and 0 = n – 1 edges, so the statement is true for 1.
To prove If the statement is true for n then it's true for n + 1, we assume the statement is true for n. That is, every tree with n vertices has n – 1 edges.
We want to prove that the statement is true for n + 1. That is, every tree with n + 1 vertices has n edges.
To do so, imagine such a tree with n + 1 vertices. Some of those vertices, at least, have degree 1. Take away one of those vertices and the edge connecting it to the rest of the tree. Now you've reduced the tree to a tree with n vertices. We've assumed that any such tree has n – 1 edges. Since this is one less than the number of edges of the original tree with n + 1 vertices, the original tree must have had n edges. That's what we wanted to prove.

A less formal way to think about the problem is this: Imagine starting with a tree with n vertices. Now add a vertex to the tree, to have n + 1 vertices. Each time you add a new vertex to the tree, you must add an edge to connect that vertex to the rest of the tree. (Adding more than one edge would produce a cycle and, by definition, a tree cannot have any cycles.) So the number of edges stays one less than the number of vertices.

This informal approach doesn't give a proof, because you need to show that any tree with n + 1 vertices has n edges, and it doesn't really show why any such tree can be built up from a tree with n vertices.

Sometimes either of these approaches can seem elusive and almost circular. Another way to understand this particular theorem is to notice that when the tree has one vertex, it has zero edges and the conjecture holds true. When the tree has two vertices, it will have one edge and the conjecture holds true. Adding a third vertex will require adding an additional edge, making there be two edges, and the conjecture holds true. You can imagine this process continuing infinitely, so that for every number of vertices it's necessary that the number of edges is one less.