a) 2k – 1
b) 2k + 1
c) 2^k + 1
d) 2^k – 1

Answer: d
Explanation: Tracing of the moves in the above ToH problem will prove this result, instead you can simply add a count for each recursive call to check the number of moves.