Proof By Induction - By Marc O Morain
How to use this applet:Read the instructions in the white box in the lower half of the applet. Use the 'next' and 'back' buttons to navigateNotes on the maths used in the applet:Proof by Induction
This is the classic "line up the dominoes, knock the first one down,
and all the other dominoes will fall too!" style of proof. It
can be very powerful when proving Theorems where some part of the
statement is controlled by a positive integer. In particular, Theorems
having to do with graphs have all sorts of integers in them! For
example, you could try to do "induction" on the number of vertices
in the graph. Or you could do induction on the number of edges.
To review, the basic Induction Principle is this:
Induction Principle: If P(n) is a statement with an integer
parameter n and the following two conditions hold:
- P(1) is true.
- For n greater than or equal to 1, If P(n) is true then P(n+1) must
also be true.
then P(n) is true for every positive number n.
Now, in Discrete Math you saw how to use induction to prove formulas,
like this:
1 + 2 + 3 + 4 + ... + n = n(n+1)/2
But in this class we'll be using induction to prove more "abstract" things.
Here's an example:
Pizza Example: Find the maximum number of pieces (not necessarilty
equally sized) that you can cut a pizza into by using n straight cuts.
We'll talk about this in class, but here's the Theorem that this problem
results in:
Theorem: If you make n straight cuts across a pizza, the most number
of pieces the pizza will be cut into is n(n+1)/2 + 1.
Proof by induction: We'll be doing induction on the number of
cuts, n.
The base case is when n=1, which cuts the pizza into two pieces, which
satsifies the formula. Cool.
Now, for the induction step we will assume that the case P(n) is true,
that is, we assume that if we make n cuts into a pizza then we can get
n(n+1)/2 + 1 pieces.
We want to show that P(n+1) is true, that is, if we make n+1 cuts
into a pizza then we can get (n+1)(n+2)/2 + 1 pieces.
OK, so we have the pizza, and we're about to make n+1 cuts to get
the most pieces possible. First let's make n of the cuts, and
by the induction hypothesis (IHOP) we know that this will
give us a max of n(n+1)/2 + 1 pieces.
Now we want to make the n+1 cut, and we want it to create as many new pieces
as possible. We will accomplish this if the n+1 cut crosses all
of the previous n cuts in different places - that is, it doesn't cut
through a point where two previous cuts meet. And if this cut crosses
n other cuts, it will create n+1 new pieces, right? (It starts off
cutting a single piece into two, then crosses a cut line, where it
cuts a second piece in two, then crosses a second cut line, etc.,
until it crosses to the other side of the pizza, cutting the last
piece it encounters in two. That's one more new piece made than the
cuts it crossed. So if it crosses n cuts it'll make n+1 new pieces.)
In other words, we know that after making n+1 cuts the most number
of pieces we can get is the number we got before plus n+1 new
pieces. That is,
number of pieces after n+1 cuts = n(n+1)/2 + 1 + (n + 1)
= n(n+1)/2 + n + 1 + 1 = ( n(n+1) + 2n + 2 ) / 2 + 1 =
(n^2 + 3n + 2)/2 + 1
= (n+1)(n+2)/2 + 1
as desired! Therefore the Theorem is true by mathematical induction.
Q.E.D.
|
