Recitation of Feb. 5, 2013

I presented the definition of a sequence (Definition 3.8 in your textbook), and sigma notation. Sigma notation can be used to sum elements of a sequence, but the elements we are summing over do not necessarily have to come from a sequence. I then went on to prove Proposition 3.12 (a) by induction.

The question was raised of whether induction is circular reasoning. It is not, but it is easy to be misled to think it is. My favorite analogy for proving a statement by induction is climbing a ladder: to show one can climb the entire ladder, one must show that it is possible to get on the first step of the ladder, and then show it is possible to go from one step to the next. No circular reasoning is involved, because at every point we are only considering previous steps in the ladder, whereas the statement to be proven talks about the entire ladder.

We discussed exercises 3.15 and 3.23 . 3.23 shows why one has to be careful when proving something by induction.

Here are some more exercises on proving a closed-form formula for a summation: 3.16, 3.27 .

Here is an interesting example of a false proof by induction: I prove that all horses have the same color by induction on the number n of horses. If there is only one horse, this is clear. Otherwise, number the horses 1,2, ..., n + 1 . The sets of horses {1,2, ..., n} and {2, ..., n + 1} each contain n elements, so by the induction hypothesis, the elements of each set share a single color. Since 2 is a member of both sets, the color must be the same for both sets. Hence all horses 1, ..., n + 1 have the same color. This completes the induction step and hence the proof.

I will let you find the mistake. In case you are stuck, Wikipedia has an entire article on this problem.