2: Induction and Recursion
( \newcommand{\kernel}{\mathrm{null}\,}\)
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).