Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers



Proof by Induction


Here we illsutrate and explain a useful justification technique called Proof by Induction. The process is described using four steps, a brief summary is provided, and some practice problems are presented.

We illustrate the process of proof by induction to show that

(I)

Process

Step 1: Verify that the desired result holds for n=1.

Here, when 1 is substituted for n in both the left- and right-side expressions in (I) above, the result is 1. Specifically

. This completes step 1.

Step 2: Assume that the desired result holds for n=k.

In our example, this means that we assume the sum of the first k positive integers is . It will be helpful to show this as

(II)

Step 2 is complete.

Step 3: Use the assumption from step 2 to show that the result holds for n=(k+1).

That is, we want to show that. In other words, show that assuming the result for n=k implies the result for n=(k+1).

Here, we build on the equation presented in (II):

If , adding (k+1) to each side assures us that

(III)

The left side of (III) is just the expansion of the expression , that is, the sum of the first (k+1) positive integers.

We are left to show that the right side of (III) is equivalent to , what our formula tells us is the correct sum.

Rewrite the right side of (III) with a common denominator:

(IV)

Now add numerators and express over the common denominator:

(V)

In the numerator of (V), k+1 is common to both terms, so we can factor the numerator, resulting in equivalent form:

(VI)

Expression (VI) is just the result we sought.

Step 4: Summarize the results of your work.

We have shown by induction that the sum of the first n positive integers can be represented by the expression .

The equation,has practical application any time we seek sums of consecutive positive integers. For example, we can now use the result to conclude that . We can also use the result to show that, for example,.

Summary

The induction process relies on a domino effect. If we can show that a result is true from the kth to the (k+1)th case, and we can show it indeed is true for the first case (k=1), we can string together a chain of conclusions: Truth for k=1 implies truth for k=2, truth for k=2 implies truth for k=3, and so on. Pushing the first domino causes all of the remaining dominoes to fall in succession.

Practice

Here are practice problems for you to complete to reinforce the induction process.

1.

Show that.

2.

Show that.

3.

Explore patterns in the sumsand so on. Use proof by induction to justify your conjecture.

4.

Show that the sum of the first n odd positive integers is .


Syllabus
Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes