A lot of the files listed below are in PDF (Adobe Acrobat) format. Alternate versions are in DVI format (produced by TeX; see see here for a DVI viewer provided by John P. Costella) and postscript format (viewable with ghostscript.) Some systems may have some problem with certain of the documents in dvi format, because they use a few German letters from a font that may not be available on some systems. (Three alternate sites for DVI viewers, via FTP, are CTAN, Duke, and Dante, in Germany.)
In a recursive algorithm, one computes the value of a function
for a particular value of N by assuming that the function's value is
already known for N-1.
Mathematical induction is the same idea, except that instead of computing a numerical value one is trying to establish the truth of a statement about N. One proves that a statement is true for N by assuming that its truth for N-1 has already been established.
Here, I illustrate this analogy by stating two classic theorems which are often proved by induction, and then giving comparable recursive algorithms.
One wants to borrow a certain amount of money for y years at a
given annual percentage rate. How does one compute
the monthly payment?
The theory of linear recurrence relations enables one to find the answer to this question.