Mathematical Induction

I’ve been reading the lucid textbook Introduction to Discrete Mathematics by Matousek and Nesetril. From the point of view of an English teacher, it really is a wonderful read. In the early chapters M&N cover basic set notation, functions, relations, equivalences, and mathematical induction. Now, mathematical induction has always given me a hard time; it’s the concept that basically kept me from pursuing a formal math education beyond calculus. But something about M&N makes it all suddenly clear to me.

Here’s my new understanding of mathematical induction:

A proof by induction consists of five basic parts: (1) hypothesis, (2) an initial test, (3) a lemma, (4) a secondary test discharging the lemma, and (5) an inductive step. Prove: the sum of all natural numbers 1 through n equals n(n + 1)/2 (Matousek and Nesetril, pg 23, exercise 1(a))

(1) 1 + 2 + … + n = n(n + 1)/2    hypothesis

(2) Let n’ = 1. Thus, 1 = 1(1 + 1)/2 = 1 is true.    initial test

(3) Let n = n’ + 1.    lemma

(4) Thus, Σn’ + n(n + 1)/2 = 1 + 1(1 + 1)/2 = 1 + 2 = 3 is true.    secondary test & discharge

(5) Σn = n(n + 1)/2 holds for all integers n, n > 0.    inductive step

Simple, eh? You could calculate the sum of all positive integers 1 through n and match each summation against n(n + 1)/2, but if you did that you’d essentially repeat steps (1) – (4) endlessly … which is why we can safely proceed to (5).

Pretty cool. Now I feel I can return to mathematics in my spare time.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: