## Some Materials for Discrete Mathematics

```
```

```
```
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.)

```
```

```
```

```
```

### Mathematical induction and recursive algorithms.

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.

```
```

```
```

```

```

```
```

```