Appendix B

This appendix is a brief disussion of the topic, and is intended to be sufficient for the times in the book that a proof uses mathematical induction.

Suppose you are given a statement, S, that depends on a variable n; for instance,

$1+{2}^{2}+\dots +{n}^{2}=\frac{n\left(n+1\right)\left(2n+1\right)}{6},n\ge 1$

Let n_{0} be the first value of n for which S applies, and prove the statement true. This is called the basis step. For our example, n_{0} = 1. Now, assume S is true for any n ≥ n_{0} and prove that this implies S is true for n + 1. This is called the inductive step.

Then,

• S is true for n_{0}, so S is true for n_{1} = n_{0} + 1.

• S is true for n_{1}, so S is true for n_{2} = ...

Start Free Trial

No credit card required