One of my teachers -- I think it was Mr Smith in "College Algebra" during my freshman year at Westminster -- gave me these words to remember:
When confronted
with a statement
that seems true
for all positive integers
the wise student
uses mathematical induction
as her proof technique.
That advice has served me well. From it I move to a pair of mathematical statements (the aforementioned Principle of Mathematical Induction and the Pigeonhole Principle) that are among my favorite mathematics poems.
Principle of Mathematical Induction
Bilingual pronunciation note: The expression S1 is read "ess-sub-one"
and other similar expressions are read similarly,
including the final Sk+1 as "ess-sub-kay-plus-one."
Suppose we have an infinite list of statements,
S1 S2, S3, . . . -- one for each positive integer.
Then all of these statements are valid
if these two conditions hold:
S1 is valid;
For any positive integer k,
if Sk is valid then so is Sk+1.
Pigeonhole Principle
Dear reader: despite its informal nature, the statement below
is a canonical instance of a very general idea -- it can, for example, be applied
to real pigeons as they nest in the compartments of a pigeon house
or to a collection of lucky numbers to be distributed to fortune-seekers.
If the apartment-house manager
has more letters to distribute
than there are pigeonholes
on the reception room wall,
then at least one pigeonhole
will get more than one envelope.
No comments:
Post a Comment