In the Tower of Hanoi game with $4$ towers, let ${W_n}$ denote the minimum number of moves needed to transfer $n$ disks from one tower to another tower. Each disk may be transferred from one tower to another, but no larger disk may be placed on top of a smaller one at any point of time.
Show that, for all $n\ge0$, $$W_{\frac{n(n+1)}{2}} \le 2^n \cdot (n-1) + 1$$
How do I prove the above inequality? Is it solving for the recurrence relation
${W_n} \le 2 \cdot W_{n-k} + 2^k - 1$, for $0 \le k \le n$ ?