Problem description:
If $W_n$ is the minimum number of moves needed to transfer a tower of $n$ disks from one peg to another when there are four pegs instead of three, show that:
$W_{n(n+1)/2} \le 2W_{n(n-1)/2} + T_n$, for $n \gt 0$.
(Here $T_n = 2^n - 1$ is the ordinary three-peg number.) Use this to find a closed form $f(n)$ such that $W_{n(n+1)/2} \le f(n)$ for all $n \ge 0$.
I am stuck on:
Use this to find a closed form $f(n)$ such that $W_{n(n+1)/2} \le f(n)$ for all $n \ge 0$.
Author argues:
If we set $Y_n = \frac{W_{n(n+1)/2} - 1}{2^n}$, we find that $Y_n \le Y_{n-1} + 1$; hence $W_{n(n+1)/2} \le 2^n(n-1) + 1$
Question:
What is the intuition behind this logic: $Y_n \le Y_{n-1} + 1$; hence $W_{n(n+1)/2} \le 2^n(n-1) + 1$ ?
I tried to rewrite it back like:
$Y_n \le Y_{n-1} + 1 => \frac{W_{n(n+1)/2} - 1}{2^n} \le \frac{W_{n(n-1)/2} - 1}{2^{n-1}} + 1$
without results.
Note that $W_1=1$, so $Y_1=0$ by definition. With $Y_k \le Y_{k-1}+1, \forall k \ge 2$ we get by repeated application that $Y_n \le n-1$. By applying the definiton of $Y_n$ the stated result follows immediately.