Question

To prove every allowable arrangement of the ndisks occurs in the solution of this variation of the puzzle.

Short answer

Hence proved.

Step-by-step solution

Given data

The Tower of Hanoi puzzle with peg 1, peg 2 and peg 3 with n disks. Each move of a disk must be a move involving peg 2 and we cannot place a disk on top a smaller disk.

Concept used of recurrence relation

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing ${\mathit{F}}_{\mathbf{n}}$as some combination of ${\mathit{F}}_{{\mathbf{i}}_{}}$ with $\mathit{i}\mathbf{<}\mathit{n}$).

Solve for possible configurations

At the time of solution no configuration can appear twice, since we have a deterministic algorithm here. If the configuration will be started with $P$and after $k$steps it will reach configuration $P$again and we will return to the same configuration after $k,2k,3k$steps also. Now, start with the starting configuration and have additional $3^n-1$distinct moves until we solve the problem. Therefore, we see that $3^n-1$configurations during the solutions, which are all the possible configurations as obtained from the part (c).