6: Induction and Recursion
- Page ID
- 60214
\( \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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
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.
You should have seen basic proofs by induction in at least one previous course. Proofs by induction are an important mathematical technique, and are often used in published papers. 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.
- 6.1: Recursively-Defined Sequences
- You may be familiar with the term “recursion” as a programming technique. It comes from the same root as the word “recur,” and is a technique that involves repeatedly applying a self-referencing definition until we reach some initial terms that are explicitly defined, and then going back through the applications to work out the result we want. If you didn’t follow that, it’s okay, we’ll go through the definition and some specific examples that should give you the idea.
- 6.2: Basic Induction
- In a proof by induction, determining that P(n0) is true for some particular integer n0 is called the base case. Proving the conditional statement that P(k)⇒P(k+1) for every k ≥ n0 is called the inductive step. The assumption we make in the inductive step, that P(k) is true for some arbitrary k ≥ n0, is called the inductive hypothesis, and can be referred to by (IH) when it is being used in the proof.
- 6.3: More Advanced Induction
- Now that we’ve reviewed the basic form of induction, it’s important to consider some more advanced forms that are often used. The first form we’ll look at is strong induction. When we have a recursively-defined sequence that depends on the previous terms, sometimes we need to know not just about the single term that comes immediately before the nth term, but about other previous terms. Only by putting all these information together will we be able to deduce the result we need about the nth term.
- 6.4: Summary
- This page contains the summary of the topics covered in Chapter 6.