Skip to main content
Mathematics LibreTexts

2: Induction and Recursion

  • Page ID
    6099
  • \( \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}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    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).

    Contributors and Attributions


    This page titled 2: Induction and Recursion is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Kenneth P. Bogart.

    • Was this article helpful?