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.The method of proof is based on adding to the list infinitely many implications:
property p is true for number 2.
property p is true for number 3.
p is true for 1.By modus ponens, if you know
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.
then you can conclude
And if you know
then you can conclude
And so on. That is, if you can prove
and all of the
then you've proved all of the
statements. In other words, if you can prove
then you've proved
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 n1 edges.
Proof: When n = 1, the tree consists of a single vertex and 0 = n 1 edges, so the statement is true for 1.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.
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.
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.
Copyright © 1999-2000 SciMathMN