second principle of mathematical induction

Second principle of mathematic induction

More commonly known as strong induction. See first principle of mathematical induction for the basic idea.

This version of induction replaces "if \[P(1)\] is true and \[P(k)\implies P(k+1)\]" with "if \[P\] is true for all \[i\] less than \[k\], then \[P\] is true for \[k\]". That's why it's called the "stronger" version as we look at more \[i\]. Intuitively, one can think of it as, in weak induction we show that one domino knocks down the next, while in strong induction we show that if all previous dominoes have been knocked over, the next one will also fall.

Let \[P(n)\] be a proposition about \[n\]. Let \[a\in \mathbb{N}\]. Suppose that:

  • \[P(a)\] is true (this is our base case, and sometimes we do have multiple base cases)
  • For all \[n\ge a\], if \[P(k)\] is true for all \[a\le k\le n\], then \[P(n+1)\] is also true

Then \[P(n)\] is true for all \[n\ge a\].

It is not necessary to start with \[P_{0}\] (although conventionally it usually starts with zero), starting with any other value is equally valid, e.g. \[P_{5}\] or \[P_{27}\].

Strong induction is useful when the result for \[n=k-1\] depends on the result for some smaller value of \[n\], but it's not the immediately previous value \[k\].

First implies second principle of mathematic induction

Assume that the two statements of strong induction is true and that we take the first principle as an axiom. We will now prove strong induction using weak induction.

Let that \[P(n)\] be some proposition for \[n\].
Let \[Q(n)\] be the proposition that \[P(k)\] is true for all \[a\le k\le n\], where \[a\in \mathbb{N}\].

Assume \[P(a)\] is true, thus \[P(k)\] is true for all \[a\le k\le a\] which implies that \[Q(a)\] is also true (base case proven).

Assume \[n\] is some arbitrary natural number and that \[Q(n)\] is true. This means \[P(k)\] is true for all \[a\le k\le n\], which by the second statement tells us that \[P(n+1)\] is also true. Therefore \[P(k)\] is true for \[a\le k\le n+1\], which in turn makes \[Q(n+1)\] true.

By weak induction, since we've proven \[Q(n)\implies Q(n+1)\], \[Q(n)\] must be true for all \[n\ge a\]. Then, since for any \[n\], \[Q(n)\] is true, it follows that \[P(n)\] is true for all \[n\ge a\].

General outline

  • Identify what we're trying to prove, i.e. the open sentence \[P(n)\]
  • Show that \[P(1)\] is true, or more generally, we show that the base cases are true, as sometimes we are required to show multiple base cases
  • Suppose that \[P(1)\] up through \[P(k)\] are true, for some natural number \[k\], then show that \[P(k+1)\] is true

Example

Prove every integer \[n\ge12\] can be written as the sum of 4s and 5s.

First, the base cases would be that \[12=4+4+4\], \[13=4+4+5\], \[14=4+5+5\], \[15=5+5+5\]. Notice that the formula for forming any value, say \[k\], larger than 15 depends on the formula to form \[k-4\]. With this realisation we can make it into a strong inductive proof as follows.

Inductive hypothesis: Suppose we make an assumption that we have shown how to sum every value from 12 through \[k\]. In logical terms, we can rewrite this as, for every integer \[n\] with \[12\le n\le k\], there exist natural numbers \[x\] and \[y\] such that \[n=4x+5y\].

Now, we show how to construct \[k+1\] with 4s and 5s. Since we've proved base cases up through 15, assume that \[k+1\ge16\]. \[k+1\ge16\implies 12\le (k+1)-4\le k\]. This inequality shows that \[n=(k+1)-4\] lies within the interval \[\left[ 12,k \right]\], thus by inductive hypothesis, \[(k+1)-4=4x+5y\], or \[k+1=4(x+1)+5y\]. This completes the induction.

Referenced by:

No backlinks found.

index