Subsection 8.8.2 Our First Example of Induction
Suppose that we want to make some sort of useful claim about the nonnegative integers (or anything else that can be characterized by them, e.g., the size of some set).
For example, suppose that we’d like to know what the sum of the first n positive integers is. In other words we want to fill in the blank here:
n1 (∑_(i = 1 )^n▒〖i=〗 )
Recall that we read the expression \(\sum_{i\ = \ 1\ }^{n}i\) as, “the sum, as i ranges from 1 to n, of i.”
A common way to proceed is in two steps:
Explore and attempt to come up with an answer that we believe to be correct.
Prove that the answer is, in fact, correct.
Mathematical induction, the proof technique that we are about to describe, is a useful tool for doing step 2. But, of course, before we can use it, we have to do step 1. Let’s continue with the summation example to see how we can do that for the summation problem. Then we’ll introduce induction to see how we can use it to prove our claim.
Think about it this problem. Can you fill in the blank? When you’re ready, turn the page and let’s discuss it.