4 rod Tower of Hanoi proof

[lemonthree]

I am having trouble solving part 2, for

$ W_{\frac{n(n+1)}{2}} \leq 2^{n} (n-1) + 1 , n \geq 0 $

I know that $W_{m} \leq 2*W_{m-k} + 2^{k} – 1, 0 \leq k \leq m$

Let $m = \frac{n(n+1)}{2}$

So now $W_{\frac{n(n+1)}{2}} \leq 2*W_{\frac{n(n+1)}{2} - k} + 2^{k} - 1, 0 \leq k \leq \frac{n(n+1)}{2}$

Let k = n (just a hunch, I can't really explain why except that because the equation has an n inside)

$W_{\frac{n(n+1)}{2}} \leq 2*W_{\frac{n(n-1)}{2}} + 2^{n} – 1$

From here, I'm not very sure, just trying to manipulate and force things in

$W_{\frac{n(n+1)}{2}} -1 \leq 2*W_{\frac{n(n-1)}{2}} + 2^{n} – 2$
And I'm lost. I tried letting $W_{\frac{n(n+1)}{2}} -1$ be $Q_{n}$ and manipulating from there such that

$Q_{n} \leq 2*Q_{n-1} + 2^{n}$ but to no avail.
So I re-worked everything and tried mathematical induction too, which I also ended up getting stuck halfway.

I think my working here is closer to the answer (and also less tedious than the induction), so I am posting this instead. Please, if there is any guidance at all, I would really appreciate it.

 

[mmwave]

Hi there,

I can see that you have made some good progress in trying to solve this inequality. I would suggest trying to simplify the expression on the right side of the inequality by using the fact that $2^{n-1} \leq 2^{n}$ for all $n \geq 0$. This will help you to get rid of the $2^{n}$ term and make the inequality easier to work with.

Also, instead of trying to manipulate the expression $W_{\frac{n(n+1)}{2}}$ directly, you can try to use the given inequality $W_{m} \leq 2*W_{m-k} + 2^{k} – 1$ to reduce the problem to a simpler one.

For example, let's say we want to show that $W_{\frac{n(n+1)}{2}} \leq 2^{n-1}(n-1) + 1$ is true. We can use the given inequality with $m = \frac{n(n+1)}{2}$ and $k = n-1$ to get:

$W_{\frac{n(n+1)}{2}} \leq 2*W_{\frac{n(n+1)}{2} - (n-1)} + 2^{n-1} – 1$

$W_{\frac{n(n+1)}{2}} \leq 2*W_{\frac{n(n-1)}{2} + 1} + 2^{n-1} – 1$

Now, we can use the fact that $W_{m} \leq 2*W_{m-1} + 2^{m} – 1$ to simplify the expression further:

$W_{\frac{n(n+1)}{2}} \leq 2*(2*W_{\frac{n(n-1)}{2}} + 2^{n-1} – 1) + 2^{n-1} – 1$

$W_{\frac{n(n+1)}{2}} \leq 2^{n-1}*(2*W_{\frac{n(n-1)}{2}} + 1)$

Now, we can use mathematical induction to show that $2*W_{\frac{n(n-1)}{2}} + 1 \