Combinatorics

Some problems can most easily be solved (or counted) with the help of a recursively-defined sequence. We'll begin this chapter by introducing these sequences.

Proofs by induction are an important mathematical technique, and are often used in published papers. This material is being presented under the assumption that you have seen elementary proofs by induction in at least one previous course. The basic explanations and examples are written with the intention of reviewing this background. If you have not encountered induction before you may wish to find supplementary introductory material and exercises. We'll do a quick review of basic proofs by induction, applying them to recursively-defined sequences. Then we'll touch on some slightly more sophisticated uses of induction. Proofs by induction will be a technique we'll use throughout the remainder of the course, in a variety of contexts.