Chapter 8.1, Problem 41E

Show that if R(n) is the number of moves used by the Frame-Stewart algorithm to solve the Reve’s puzzle with n disks, where k is chosen to be the smallest integer with $n\le k\left(k+1\right)/2$ , then R(n) satisfies the recurrence relation $R\left(n\right)=2R\left(n-k\right)+2^k-1$ , with $R\left(0\right)=0$ and $R\left(1\right)=1$ .