# 6: Induction and Recursion

• • Joy Morris
• University of Lethbridge
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\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.