Suppose P(n) is a statement for each natural number n. If
ì ï í
ï î
P(1)istrue,
WheneverP(k)istrue,P(k+1)istrue.
then
P(n)istrueforalln Î N.
A proof using PMI requires:
·
Carefully stating the proposition or
statement P(k), which may be a sentence (paragraph) or
equation, inequality, ¼, which depends on k.
·
Proving that P(1) is true - usually a simple
verification.
·
Assume P(k)1 - write down the statement or formula
P(k):
·
Assume ¼
(statement or formula which depends on k).
·
Apply valid operations (theorems,
add to both sides of an equation, etc.) ¼ Remember that P(1) is valid too.
Try to arrive at P(k + 1) as a statement or equation.
Examples
1.
Prove the formula
12 + 22 + ¼+ n2 =
n (n + 1) (2 n + 1)
6
.
·
P(n) is the sentence
12 + 22 + ¼+ n2 =
n (n + 1) (2 n + 1)
6
.
What is the verb of the sentence?
·
P(1) is true means to verify the statement
12 =
1 (1 + 1) (2 ·1 + 1)
6
.
·
P(n) is true implies P(n + 1) is true
means to assume
12 + 22 + ¼+ n2 =
n (n + 1) (2 n + 1)
6
,
and to show that
12 + 22 + ¼+ n2 + (n + 1)2 =
(n + 1) ((n + 1) + 1) (2 (n + 1) + 1)
6
The valid operations are adding (n + 1)2 to both
sides of the equation P(n) and various algebraic manipulations.
2.
Tower of Hanoi
·
P(n) is the statement:
·
n rings can be moved from one spindle to another
with 2n - 1 moves, and no fewer.
Other manageable forms of P(n) are
·
The minimal number of
moves to move n rings from one spindle to another is 2n - 1.
·
It takes 2n - 1 moves
to move n rings from one spindle to another.
·
P(1) is easy.
·
P(n) is true implies P(n + 1) is true
means to assume n rings can be moved from one spindle to
another
with 2n - 1 moves, and no fewer , and to show that
n + 1 rings can be moved from one spindle to another
with 2n + 1 - 1 moves, and no fewer .
In this case, the valid operations are a
precise sequence of moves to move the n+1 rings - the top n
rings are moved using P(n), the bottom ring is moved and
then the top rings are moved a second time using P(n).
More on the Tower of Hanoi
Let M(k) be the minimal number of moves.
·
P(k): M(k) = 2 k -1.
·
Verify P(1): M(1) = 21 - 1 = 1.
Move the single ring from 1 to 3.
·
Assume P(k): M(k) = 2 k -1.
Now let there be k + 1 rings be stacked on pole 1. The bottom
ring can be moved only to an empty pole. So the bottom ring can be
moved from Pole 1 to Pole 3 iff Pole 3 is empty! Therefore moving
the bottom ring from Pole 1 [2] to Pole 3 requires that the top
k rings be stacked on Pole 2 [1] - this operation requires
M(k) = 2 k -1 moves. So the minimal number of moves for k+1
rings is determined by the following valid operations :
1.
Move the top k rings from Pole 1 to Pole 2 using M(k)
moves,
2.
Move the bottom ring from Pole 1 to Pole 3 in 1 move,
3.
Move the k rings from Pole 2 to Pole 3 using M(k)
moves.
The strategy is minimal since moving the bottom ring from Pole 1
to Pole 3 requires at least M(k) + 1 moves.
Then, using P(k), M(k + 1) = M(k) + 1 + M(k) = ¼ = 2k+1 -1.
We have actually constructed the sequence M(k), k = 1, 2,¼, by recursion ,
M(1)
= 1
M(k + 1)
= 2 M(k) + 1 , k = 1, 2, ¼.
Real Numbers and Binary Expansions
The real numbers in R are identified with points on a
horizontal line. For the time being, we will identify a real
number x with a decimal expansion .
·
Every decimal expansion represents a real number x:
x
= ±N.d1d2¼,
dk
Î {0,1, ... ,9}.
This is the statement that every infinite series of the form
d1 10-1 + d2 10-2 + ¼, dk Î {0,1, ... ,9},
converges.
Just as well we could identify a real
number x with a binary expansion .
·
Every binary expansion represents a real number x:
x
= ±N.binb1b2¼,
bk
Î {0,1}.
This is the statement that every infinite series of the form
b1 2-1 + b2 2-2 + ¼, bk Î {0,1},
converges.
Construction of the Binary Expansion by Recursion
A demonstration of a construction of the the binary expansion
of a real number x on the line, 0 £ x < 1, will be presented in class.
Footnotes:
1As a variant, assume that P(1), ¼, P(k), are true and use PCI.
File translated from
TEX
by
TTH,
version 3.77. On 05 Sep 2007, 06:14.