Variants of induction

From CS2800 wiki

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.