# Mathematical Induction

June 17, 2010 Leave a comment

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.