# 2: Induction and Recursion

$$\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}}$$

If you are unfamiliar with the Principle of Mathematical Induction, you should read Appendix B. The principle of mathematical induction states that In order to prove a statement about an integer $$n$$, if we can $$1$$. Prove the statement when $$n = b$$, for some fixed integer $$b$$, and $$2$$. Show that the truth of the statement for $$n = k − 1$$ implies the truth of the statement for $$n = k$$ whenever $$k > b$$, then we can conclude the statement is true for all integers $$n ≥ b.$$

• 2.1: Some Examples of Mathematical Introduction
The principle of mathematical induction states that in order to prove a statement about an integer n, if we can 1) Prove the statement when n = b, for some fixed integer b, and 2) Show that the truth of the statement for n = k−1 implies the truth of the statement for n = k whenever k > b, then we can conclude the statement is true for all integers n ≥ b.
• 2.2: Recurrence Relations
A linear recurrence is one in which an is expressed as a sum of functions of n times values of (some of the terms) a_i for i < n plus (perhaps) another function (called the driving function) of n. A linear equation is called homogeneous if the driving function is zero (or, in other words, there is no driving function). It is called a constant coefficient linear recurrence if the functions that are multiplied by the a_i terms are all constants (but the driving function need not be constan
• 2.3: Graph and Trees
In Section 1.3.4 we introduced the idea of a directed graph. Graphs consist of vertices and edges. We describe vertices and edges in much the same way as we describe points and lines in geometry: we don’t really say what vertices and edges are, but we say what they do. We just don’t have a complicated axiom system the way we do in geometry. A graph consists of a set V called a vertex set and a set E called an edge set. Each member of V is called a vertex and each member of E is called an edge.
• 2.4: Applications of Induction and Recursion in Combinatorics and Graph Theory (Exercises)
This section contains the supplementary problems related to the materials discussed in Chapter 2.

Thumbnail: A drawing of a graph. (Public Domain; AzaToth).