**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.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.

etc.

p is true for 1.By

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.

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

and

then you've proved

**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 withThen the statementnvertices hasn– 1 edges.

Proof: WhenA less formal way to think about the problem is this: Imagine starting with a tree withn= 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 forwe assume the statement is true forn+ 1,n.That is, every tree withnvertices hasn– 1 edges.We want to prove that the statement is true for

n+ 1. That is, every tree withn+ 1 vertices hasnedges.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 withnvertices. We've assumed that any such tree hasn– 1 edges. Since this is one less than the number of edges of the original tree withn+ 1 vertices, the original tree must have hadnedges. 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