PreTeXt Sample Book: Abstract Algebra (SAMPLE ONLY)

<section xml:id="section-math-induction">
  <title>Mathematical Induction and Math in a Title <m>A\notsubset B</m></title>
  <p>
    Suppose we wish to show that
    <me>
      1 + 2 + \cdots + n = \frac{n(n + 1)}{2}
    </me>
    for any natural number <m>n</m>.
    This formula is easily  verified for small numbers such as <m>n = 1</m>, 2, 3, or 4, but it is impossible to verify for all natural numbers on a case-by-case basis.
    To prove the formula true in general,
    a more generic method is required.
  </p>
  <p>
    Suppose we have verified the equation for the first <m>n</m> cases.
    We will attempt to show that we can generate the formula for the <m>(n + 1)</m>th case from this knowledge.
    The formula is true for <m>n = 1</m> since
    <me>
      1 = \frac{1(1 + 1)}{2}
    </me>.
    If we have verified the first <m>n</m> cases, then
    <md>
      <mrow>1 + 2 + \cdots + n + (n + 1) &amp; = \frac{n(n + 1)}{2} + n + 1</mrow>
      <mrow>&amp; = \frac{n^2 + 3n + 2}{2}</mrow>
      <mrow>&amp; = \frac{(n + 1)[(n + 1) + 1]}{2}</mrow>
    </md>.
  </p>
  <p>
    This is exactly the formula for the <m>(n + 1)</m>th case.
  </p>
  <p>
    This method of proof is known as
    <term>mathematical induction</term>.
    Instead of attempting to verify a statement about some subset <m>S</m> of the positive integers
    <m>{\mathbb N}</m> on a case-by-case basis,
    an impossible task if <m>S</m> is an infinite set,
    we give a specific proof for the smallest integer being considered,
    followed by a generic argument showing that if the statement holds for a given case,
    then it must also hold for the next case in the sequence.
    We summarize mathematical induction in the following axiom.
  </p>
  <principle>
    <title>First Principle of Mathematical Induction</title>
    <idx><h>Induction</h><h>first principle of</h></idx>
    <statement>
      <p>
        Let <m>S(n)</m> be a statement about integers for
        <m>n \in {\mathbb N}</m> and suppose <m>S(n_0)</m> is true for some integer <m>n_0</m>.
        If for all integers <m>k</m> with <m>k \geq n_0</m>,
        <m>S(k)</m> implies that <m>S(k+1)</m> is true,
        then <m>S(n)</m> is true for all integers <m>n</m> greater than or equal to <m>n_0</m>.
      </p>
    </statement>
  </principle>

  <example xml:id="example-integers-induction-greater-than">
    <title>An Inequality for Powers of <m>2</m></title>
    <p>
      For all integers <m>n \geq 3</m>, <m>2^n \gt n + 4</m>.
      Since
      <me>
        8 = 2^3 \gt 3 + 4 = 7
      </me>,
      the statement is true for <m>n_0 = 3</m>.
      Assume that <m>2^k \gt k + 4</m> for <m>k \geq 3</m>.
      Then <m>2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)</m>.
      But
      <me>
        2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4
      </me>
      since <m>k</m> is positive.
      Hence, by induction,
      the statement holds for all integers <m>n \geq 3</m>.
    </p>
  </example>
  <example xml:id="example-integers-induction-divisible">
    <title>Some Integers Divisible by <m>9</m></title>
    <p>
      Every integer <m>10^{n + 1} + 3 \cdot 10^n + 5</m> is divisible by 9 for <m>n \in {\mathbb N}</m>.
      For <m>n = 1</m>,
      <me>
        10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15
      </me>
      is divisible by 9.
      Suppose that <m>10^{k + 1} + 3 \cdot 10^k + 5</m> is divisible by 9 for <m>k \geq 1</m>.
      Then
      <md>
        <mrow>10^{(k + 1) + 1} + 3 \cdot 10^{k + 1} + 5&amp; = 10^{k + 2} + 3 \cdot 10^{k + 1} + 50 - 45</mrow>
        <mrow>&amp; = 10 (10^{k + 1} + 3 \cdot 10^{k} + 5) - 45</mrow>
      </md>
      is divisible by 9.
    </p>
  </example>
  <example xml:id="example-integers-binomial-theorem">
    <title>The Binomial Theorem</title>
    <p>
      We will prove the binomial theorem using mathematical induction; that is,
      <me>
        (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}
      </me>,
      where <m>a</m> and <m>b</m> are real numbers,
      <m>n \in \mathbb{N}</m>, and
      <me>
        \binom{n}{k} = \frac{n!}{k! (n - k)!}
      </me>
      is the binomial coefficient.
      We first show that
      <me>
        \binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}
      </me>.
      This result follows from
      <md>
        <mrow>\binom{n}{k} + \binom{n}{k - 1} &amp; = \frac{n!}{k!(n - k)!} +\frac{n!}{(k-1)!(n - k + 1)!}</mrow>
        <mrow>&amp; = \frac{(n + 1)!}{k!(n + 1 - k)!}</mrow>
        <mrow>&amp; =\binom{n + 1}{k}</mrow>
      </md>.
      <notation>
        <usage><m>n!</m></usage>
        <description><m>n</m> factorial</description>
      </notation>
      <notation>
        <usage><m>\binom{n}{k}</m></usage>
        <description>binomial coefficient <m>n!/(k!(n-k)!)</m></description>
      </notation>
    </p>
    <p>
      If <m>n = 1</m>, the binomial theorem is easy to verify.
      Now assume that the result is true for <m>n</m> greater than or equal to 1.
      Then
      <md>
        <mrow>(a + b)^{n + 1} &amp; = (a + b)(a + b)^n</mrow>
        <mrow>&amp; = (a + b) \left( \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\right)</mrow>
        <mrow>&amp; = \sum_{k = 0}^{n} \binom{n}{k} a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n + 1 - k}</mrow>
        <mrow>&amp; = a^{n + 1} + \sum_{k = 1}^{n} \binom{n}{k - 1} a^{k} b^{n + 1 - k} + \sum_{k = 1}^{n} \binom{n}{k}  a^k b^{n + 1 - k} + b^{n + 1}</mrow>
        <mrow>&amp;  = a^{n + 1} + \sum_{k = 1}^{n} \left[ \binom{n}{k - 1} + \binom{n}{k} \right]a^k b^{n + 1 - k} + b^{n + 1}</mrow>
        <mrow>&amp;  = \sum_{k = 0}^{n + 1}   \binom{n + 1}{k} a^k b^{n + 1- k}</mrow>
      </md>.
    </p>
  </example>
  <p>
    We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.
  </p>
  <principle>
    <title>Second Principle of Mathematical Induction</title>
    <idx><h>Induction</h><h>second principle of</h></idx>
    <statement>
      <p>
        Let <m>S(n)</m> be a statement about integers for
        <m>n \in {\mathbb N}</m> and suppose <m>S(n_0)</m> is true for some integer <m>n_0</m>.
        If <m>S(n_0), S(n_0 + 1), \ldots, S(k)</m> imply that
        <m>S(k + 1)</m> for <m>k \geq n_0</m>,
        then the statement <m>S(n)</m> is true for all integers <m>n \geq n_0</m>.
      </p>
    </statement>
  </principle>

  <p>
    A nonempty subset <m>S</m> of
    <m>{\mathbb Z}</m> is <term>well-ordered</term>
        <idx><h>Well-ordered set</h></idx>
    if <m>S</m> contains a least element.
    Notice that the set <m>{\mathbb Z}</m> is not well-ordered since it does not contain a smallest element.
    However, the natural numbers are well-ordered.
  </p>
  <principle>
    <title>Principle of Well-Ordering</title>
    <statement>
      <p>
        Every nonempty subset of the natural numbers is well-ordered.
      </p>
    </statement>
  </principle>
  <p>
    The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.
  </p>
  <lemma xml:id="lemma-integers-smallest-number">
    <statement>
      <p>
        The Principle of Mathematical Induction implies that <m>1</m> is the least positive natural number.
      </p>
    </statement>
    <proof>
      <p>
        Let <m>S = \{ n \in {\mathbb N} : n \geq 1 \}</m>.
        Then <m>1 \in S</m>.
        Now assume that <m>n \in S</m>;
        that is, <m>n \geq 1</m>.
        Since <m>n+1 \geq 1</m>, <m>n+ 1 \in S</m>;
        hence, by induction,
        every natural number is greater than or equal to 1.
      </p>
    </proof>
  </lemma>


  <theorem xml:id="theorem-integers-pmi-implies-pwo">
    <statement>
      <p>
        The Principle of Mathematical Induction implies the Principle of Well-Ordering.
        That is, every nonempty subset of
        <m>\mathbb N</m> contains a least element.
      </p>
    </statement>
    <proof>
      <p>
        We must show that if <m>S</m> is a nonempty subset of the natural numbers,
        then <m>S</m> contains a least element.
        If <m>S</m> contains 1, then the theorem is true by <xref ref="lemma-integers-smallest-number" />.
        Assume that if <m>S</m> contains an integer <m>k</m> such that <m>1 \leq k \leq n</m>,
        then <m>S</m> contains a least element.
        We will show that if a set <m>S</m> contains an integer less than or equal to <m>n + 1</m>,
        then <m>S</m> has a least element.
        If <m>S</m> does not contain an integer less than <m>n+1</m>,
        then <m>n+1</m> is the smallest integer in <m>S</m>.
        Otherwise, since <m>S</m> is nonempty,
        <m>S</m> must contain an integer less than or equal to <m>n</m>.
        In this case, by induction, <m>S</m> contains a least element.
      </p>
    </proof>
  </theorem>

  <p>
    Induction can also be very useful in formulating definitions.
    For instance, there are two ways to define <m>n!</m>,
    the factorial of a positive integer <m>n</m>.
    <ul>
      <li>
        <p>
          The <em>explicit</em> definition:
          <m>n! = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n</m>.
        </p>
      </li>
      <li>
        <p>
          The <em>inductive</em> or <em>recursive</em> definition:
          <m>1! = 1</m> and <m>n! = n(n - 1)!</m> for <m>n \gt 1</m>.
        </p>
      </li>
    </ul>
  </p>
  <p>
    Every good mathematician or computer scientist knows that looking at problems recursively,
    as opposed to explicitly,
    often results in better understanding of complex issues.
  </p>
</section>