Show that if R(n) is the number of moves used by the Frame-Stewart algorithm to solve the

Question:

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 ≤ k(k + 1)/2, then R(n) satisfies the recurrence relation R(n) = 2R(n − k) + 2k − 1, with R(0) = 0 and R(1) = 1.