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