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.

No comments:

Post a Comment