Proof by Induction, Part 1

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Proof by Induction

Based on section 4.1 in the textbook and this discussion of induction proofs.

Examples

Sum of Even Numbers

From the discussion: prove that the sum of the first n even natural numbers is n(n+1).

Induction seems like a good way to prove this, since it’s a proposition about the natural numbers, which is the set of numbers that induction works most naturally with, and sums often break down into smaller sums in ways that work well with induction.

To do an induction proof, we need two things:

• A basis step, i.e., a part of the proof where we prove that the proposition holds for the smallest possible number
• An induction step, i.e., a part of the proof where we prove that if the proposition holds for some number, then it must hold for the next. A couple of notes are in order on induction steps:
  • Since the induction step is proving a conditional statement, it always involves assuming that the proposition holds for some unknown value, often called k. You then need to use this assumption to show that the proposition holds for the next (integer) value, k+1.
  • Informally, think of the induction step and basis step working together: the basis step shows that there’s some number the proposition holds for, commonly 1. Then by the induction step, if the proposition holds for 1, it must hold for 2. Then, also by the induction step, if it holds for 2, it must hold for 3. Then for 4. And 5. And so on for all integers greater than the basis step’s value.
  • A more formal way to understand the induction step is that it’s establishing that the set of numbers for which the proposition holds is inductive. The basis step then establishes that it holds for some integer, and any inductive set that contains that number also contains all larger integers.

We wrote the complete proof out in LaTeX, to see what an induction proof might look like when formally written out. You can get the source and PDF files from Canvas.

This example also demonstrated several new features of LaTeX:

• The \sum command generates big-Sigma summation notation.
• The \label and \ref commands allow LaTeX to do cross-references for you. Put \label{name} inside some numbered environment that you want to reference elsewhere, and then use \ref{name} to generate the corresponding number wherever you want it. In both commands, name is a name you choose, and that will refer to the item with \label inside it. See the LaTeX source for this proof for examples.

Sum of Natural Numbers

The textbook’s Progress Check 4.3: prove that the sum of the first n natural numbers is n(n+1)/2.

We outlined an induction proof for this proposition. It’s an exercise for the reader to write it out formally in LaTeX or some similar tool if you want the practice.

For the basis step, let n = 1: Then the sum of the first 1 natural numbers is just 1, which equals 1(1+1)/2.

For the induction step, assume the sum of the first k natural numbers is k(k+1)/2, i.e., that 1 + 2 + 3 + … + k = k(k+1)/2. Then show that 1 + 2 + 3 + … + k + (k+1) = (k+1)(k+2)/2.

To do this, break up 1 + 2 + 3 + … + k + (k+1) as (1 + 2 + 3 + … + k) + (k+1). The first part of this equals k(k+1)/2, by the induction hypothesis. The complete sum is therefore k(k+1)/2 + (k+1).

Put these two terms over a common denominator and simplify to get (k+1)(k+2)/2.

Problem Set 7

…Is now ready in Canvas.

It exercises proof by cases and proofs by induction. See the handout for details.

Finish it by next Monday (April 5) and grade it by the following Monday (April 12).

Next

Keep looking at examples of induction proofs.

No new reading, but review section 4.1 if you want.

Also keep trying induction proofs on your own in the induction proof discussion.

Next Lecture