## Friday, July 29, 2011

### Mathematical Induction -- principle, perhaps poem

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.