Tower of Hanoi L - rule:
1. must move one disk at a time;
2. a larger disk cannot be on top of any smaller disks at any time
3. do it in as few moves as possible
 |
| 2 Disks |
 |
| 3 Disk |
 |
| 4 Disk
Mathematical induction is a general way to prove that some statement
about the integer n is true for all n _ n0. First, we prove the statement
when n has its smallest value, n0; this is called the basis. Then we prove the
statement for n > n0, assuming that it has already been proved for all values
between n0 and n - 1, inclusive; this is called the induction. Such proof
gives in_nitely many results with only a _nite amount of work.
Recurrences are ideally set up for mathematical induction. In our case,
for example, follows easily from The basis is trivial, since T0 =
20 -1 = 0. And the induction follows for n > 0 if we assume that holds
when n is replaced by n - 1:
Tn = 2Tn-1 + 1
= 2(2n-1 - 1) + 1
= 2n - 1 :
Hence (1.2) holds for n as well. Good! Our quest for Tn has ended successfully.
|
