The object of this game is to move N disks from left peg to right peg using middle peg as an auxiliary holding peg. At no time may a larger disk be placed on a smaller disk. The figure represents starting state for N=3 disks.

## Proof

It can be shown by principle of mathematical induction that this can be solved for any arbitrarily large values of N.

Basis: A single disk can be moved from left peg to right peg. So, base case is trivially true.

Hypothesis: Let us assume that this problem can be solved for k disks. Hence, k disks can be moves from one peg to another using an auxiliary peg. P(k) is assumed to bue.re t

Inductive Step: If this holds for k disks, then move k disks to middle peg using right peg as an auxiliary peg. Then, move (k+1)th disk to the right peg. Then move k disks from middle peg to right peg. Hence, whenever we can move k disks, we can also move k+1 disks.

thereby showing that indeed P(k + 1) holds.

Since both the basis and the inductive step have been performed, by mathematical induction, the statement P(n) holds for all natural numbers n. Q.E.D.

## Logic

Here is a recursive program that solves the puzzle in prolog. It consists of two clauses.

```move(1,X,Y,_):-write('move top disk from '),write(X),write(' to '),write(Y),nl.
```
```move(N,X,Y,Z):-N>1,M=N-1,move(M,X,Z,Y),move(1,X,Y,_),move(M,Z,Y,X).
```