Sunday, April 20, 2008

What is Mathematics: Mathematical Induction

This is the first in my series on some interesting and important techniques and results described in the book What is Mathematics. The first chapter introduces the natural numbers, 1, 2, 3, ... In Leopold Kronecker's words: "God created the natural numbers; everything else is man's handiwork."

After introducing the basics of natural numbers, the authors introduce the fundamental technique of the principle of mathematical induction. This is a very simple, yet powerful, method for proving theorems about an infinite sequence of cases. In its simplest form, suppose you want to prove that a property An for all positive integers n (e.g., An might be the proposition that (1 + p)n ≥ (1 + np) for any p > -1). The principle of mathematical induction states that you can prove this using two steps:
  1. First, you prove that A1 holds, i.e., the property holds when n = 1 (often called the base case).
  2. Next, for every r ≥ 1 you show that if Ar holds then Ar+1 also holds (this is often called the inductive step).
One can see that the above two steps serve to establish An for all n ≥ 1.
The proposition that (1 + p)n ≥ (1 + np) for any p > -1 can be easily established using mathematical induction (this will prove to be a useful little inequality).

The principle of mathematical induction needs to be applied with care. The authors demonstrate the pitfalls of this method with the following "proof" that all numbers are, in fact, equal!

Let An be the statement "If a and b are any two positive integers such that max(a, b) = n, then a = b". The base case is certainly true: when n = 1, a and b must both be 1 (being positive integers). For the inductive case, assume Ar holds and let a and b be such that max(a, b) = r + 1. Clearly, then max(a - 1, b - 1) = r, and hence by assumption a - 1 = b - 1. Hence a = b. So An holds for all n. In particular, for any a and b, if max(a, b) = r, then Ar holds and hence for any a and b, a = b!

Can you see the hole in this proof?

What is Mathematics

In a previous post I mentioned that I was going to get a copy of the book What is Mathematics by Richard Courant and Herbert Robbins. Well, I've now got a copy of it and I'm reading through it. And I'm thoroughly enjoying it! The book is a mathematics book---it talks about the techniques and results in mathematics, often with proofs (at least when the proofs don't involve advanced techniques). But it's written in a very conversational style---as if Courant was sitting across the dining table from you and sharing with you his love of mathematics. (That imagery makes sense only if you can imagine discussing mathematics at the dinner table...:-)

As I read this book, I thought I'd put together a series of posts highlighting some of the most interesting and important methods and theorems that I encounter. Part of my purpose is to share this with you (and encourage you to get the book); but the other part is to summarize it for my own benefit. I'll keep this post updated with the list of all posts in this series. Here are the posts.
  1. Mathematical induction
  2. Prime numbers
  3. GCD

Thursday, April 3, 2008

International Bar-Code of Life

My friend Alon has a great post about his recent visit to Costa Rica where he learned about the International Bar-Code of Life Project from his host Dan Janzen, a Kyoto Prize winning biologist.
/* Google Analytics tracking */