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.