Induction

From CS2800 wiki
(Redirected from Inductive)

Induction can refer to weak induction, strong induction, or structural induction. In all cases, induction is a method for proving a statement [math]P(x) [/math] about a "complex" element [math]x [/math] of a set by reducing it to a "simpler" case.

In the context of induction, the predicate [math]P(x) [/math] is often referred to as the "inductive hypothesis"

Weak induction

If [math]P(n) [/math] is a statement, and you wish to prove "for all [math]n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/Natural_number}{\mathbb{N}} [/math], P(n)," one way to do so is using weak induction.

To prove "[math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \href{/cs2800/wiki/index.php/%5Cin}{\in} \mathbb{N},P(n) [/math]" using weak induction, you must prove [math]P(0) [/math] (this is often called the base case), and then you must prove [math]P(n+1) [/math] for an arbitrary [math]n [/math], assuming [math]P(n) [/math] (this is called the inductive step).

In the context of an inductive proof, [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] is referred to as the inductive hypothesis

See induction overview for an intuitive explanation of why weak induction works.

There are many variants of induction: For example, in the inductive step, you may assume [math]P(n-1) [/math] and prove [math]P(n) [/math]:

To prove [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php?title=Natural_numbers&action=edit&redlink=1}{\mathbb{N}} [/math] by weak induction, you can prove [math]P(0) [/math] and prove [math]P(n) [/math] for an arbitrary [math]n\gt 0 [/math], assuming [math]P(n-1) [/math].

This is just a change of variables, but it occasionally makes the notation a bit easier to work with.


There are other variants that you can use. For example, if you only care about [math]P(n) [/math] for [math]n \geq k [/math], you can use the following principle:

To prove [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \geq k, P(n) [/math] using weak induction, you can prove [math]P(k) [/math] and prove [math]P(n+1) [/math] for an arbitrary [math]n \geq k [/math], assuming [math]P(n) [/math].

This is also equivalent to weak induction.


In fact, one can even convert a proof by strong induction into a proof by weak induction.


You can mix and match these variations. If you're using an unfamiliar variation, you should check that it makes sense intuitively, and if possible, show how to convert it to a proof by weak induction. For example, you should be sure to avoid a backwards proof while doing induction.

Strong induction

Strong induction is similar to weak induction, except that you make additional assumptions in the inductive step.

To prove "for all [math]n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], P(n)" by strong induction, you must

  • prove [math]P(0) [/math] (this is called the base case), and
  • for an arbitrary [math]n [/math], prove [math]P(n) [/math], assuming [math]P(n-1),P(n-2),\dots,P(0) [/math] (this is the inductive step)

More concisely, the inductive step requires you to prove [math]P(n) [/math] assuming [math]P(k) [/math] for all [math]k \lt n [/math].

The difference between strong induction and weak induction is only the set of assumptions made in the inductive step.

The intuition for why strong induction works is the same reason as that for weak induction: in order to prove [math]P(5) [/math], for example, I would first use the base case to conclude [math]P(0) [/math]. Next, I would use the inductive step to prove [math]P(1) [/math]; this inductive step may use [math]P(0) [/math] but that's ok, because we've already proved [math]P(0) [/math]. I would then use the inductive step to conclude [math]P(2) [/math]; this may use both [math]P(0) [/math] and [math]P(1) [/math], but that's okay because we've already proved [math]P(0) [/math] and [math]P(1) [/math]. Next, I would again use the inductive step to conclude [math]P(3) [/math]; as before, this may use [math]P(0) [/math], [math]P(1) [/math], or [math]P(2) [/math], but this is not a problem since we have already proved those three facts. Similarly, we can use the inductive step to conclude P(4), P(5), etc.

Note that you can always use strong induction instead of weak induction. Using weak induction is just a matter of style: by avoiding unneeded assumptions, you reduce the complexity of your proof, and clearly indicate to the reader what assumptions you are actually planning to use. I often start inductive proofs by not specifying whether they are proofs by strong or weak induction; once I know which inductive hypothesis I actually need, I go back and fill in the beginning of my inductive step.