# 5: Proof Techniques II - Induction

- Page ID
- 19394

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Who was the guy who first looked at a cow and said, ”I think I’ll drink whatever comes out of these things when I squeeze ’em!”?

–Bill Watterson

- 5.1: The Principle of Mathematical Induction
- The Principle of Mathematical Induction (PMI) may be the least intuitive proof method available to us. Indeed, at first, PMI may feel somewhat like grabbing yourself by the seat of your pants and lifting yourself into the air. Despite the indisputable fact that proofs by PMI often feel like magic, we need to convince you of the validity of this proof technique. It is one of the most important tools in your mathematical kit!

- 5.2: Formulas for Sums and Products
- Gauss, when only a child, found a formula for summing the first 100 natural numbers (or so the story goes. . . ). This formula, and his clever method for justifying it, can be easily generalized to the sum of the first n naturals. While learning calculus, notably during the study of Riemann sums, one encounters other summation formulas. For this reason, somewhere in almost every calculus book one will find the following formulas collected.

- 5.3: Divisibility Statements and Other Proofs Using PMI
- There is a very famous result known as Fermat’s Little Theorem. This would probably be abbreviated FLT except for two things. In science fiction FLT means “faster than light travel” and there is another theorem due to Fermat that goes by the initials FLT: Fermat’s Last Theorem.

- 5.4: The Strong Form of Mathematical Induction
- The strong form of mathematical induction (a.k.a. the principle of complete induction, PCI; also a.k.a. course-of-values induction) is so-called because the hypotheses one uses are stronger.