Answer / Explanation:
We should note that this is a recursive algorithm and therefore the algorithm will move the to n disks from the source peg src (either 1 or 2 ) to the destination Peg dst ( either 1 or 2) where every move uses Peg 0.
We should also note that the forbidden peg never moves or changes, so we can code it into an algorithm which states thus:
F H ( n, src, dst)
if n > 0
F H ( n - 1, src, dst)
move disk n from Peg src to peg 0
F H ( n - 1, dst, src )
move disk n from Peg 0 to peg dst
F H ( n - 1, src, dst)
Where the initial call is F H (n, 1, 2).
Therefore, the number of moves satisfies the recurrence T(n) =3T (n - 1) + 2. Therefore, We can easily verify by induction that T(n) = 3n - 1.
Here is a complete proof of correctness of the algorithm.
Let "n" be an arbitrary non-negative integer,and assume that F H (m,a,b) correctly moves "m" disks from "a" to "b" for every non-negative integer m<n. If therefore, n=0, the algorithm correctly does nothing
so assume n > 0. By the inductive hypothesis, the first recursive call correctly moves the top n-1 disks from src - to - dst.
The second line moves disk "n" from src - to peg 0 which is legal because all smaller disks are on peg dst.
By the inductive hypothesis, the second recursive call correctly moves the top n-1 disks from dst - to - src. The fourth line moves disk n from peg to dst which is legal because all smaller disks are on peg src. Finally, by the inductive hypothesis,the first recursive call correctly moves the top n-1 disks from src - to - dst.