# Concrete mathematics exercise 1.17 upper bound intuition

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.