\documentclass[a4paper]{report}
\input{preamble.tex}

\title{MH1301 Bonus Question 2}

\begin{document}
\maketitle

\noindent
1. To show that the following equality holds:
\[
W_m \leqslant 2W_{m-k} + 2^{k}-1.
\]
We must imagine a tower of Hanoi where there is a tower of plates of size $m$.
This means that it comprises of $(m-k)+k$ plates.
So we imagine the stack of plates as two stacks stacked on top of each other.
The stack on top has size $m-k$, and the stack below is of size $k$.

\bigbreak
Then, if we want to move all the plates from the first pole to the last pole, we can first move the first $m-k$ stack of plates to one of the auxiliary poles.
This step will take at minimum $W_{m-k}$ moves since there are two auxiliary poles that can be used.

\bigbreak
After this step, we can shift the remaining $k$ plates from the first pole to the last pole.
This step will take $2^{k}-1$ moves since one of the auxiliary rods cannot be used, making it the same form as the original tower of Hanoi puzzle.

\bigbreak
After this step, we complete by moving the remaining $m-k$ plates from the auxiliary rod to the final rod.
This step will again take at minimum $W_{m-k}$ moves since there are two auxiliary poles that can be used.

\bigbreak
\noindent
Thus we have the following method of moving a stack of size $m$ for four poles:
\[
	W_{m-k} + (2^{k}-1) + W_{m-k}.
\]
Which evaluates to:
\[
	2W_{m-k}+2^{k}-1.
\]
Since this is one possible method for transferring the plates, we can say that the minimum number of moves will definitely not be more than this number, therefore we can say the following:
\[
W_m \leqslant 2W_{m-k} + 2^{k}-1.
\]

\bigbreak
\noindent
2. To show that the following equality holds:
\[
	W_{\frac{n(n+1)}{2}} \leqslant 2^{n}(n-1) +1.
\]
We must first notice that:
\[
	\frac{n(n+1)}{2} = \sum_{i = 1}^n i.
\]
So we recognise that $W_{\frac{n(n+1)}{2}}$ is the minimum number of moves to transfer a stack of plates from the first pole to the last pole where there are:
\[
	n + (n-1) + (n-2) + \dotsb + 2 + 1.
\]
plates. This can be broken down to be seen as a stack with $n$ sub stacks, with the sub stack of size $n$ at the bottom, followed by a sub stack few size $n-1$ right on top of it, so on and so forth, until there is the smallest sub stack of size one at the top.

\bigbreak
Let us say that stack of plates which have a total number of plates of the form $W_{\frac{n(n+1)}{2}}$ can be rewritten as $W_{S(n)}$ to denote stacks that have a size of $n + (n-1) + (n-2) + \dotsb + 1$.
Thus from the inequality shown in part one we have the following:
\begin{align*}
	W_{S(n)} & \leqslant 2W_{S(n-1)} + 2^{n}-1\\
		 & \leqslant 2(2W_{S(n-2)} + 2^{n-1}-1) + 2^{n}-1\\
		 & \leqslant 2^2 W_{S(n-2)} + 2\cdot 2^{n-1}-2 + 2^{n}-1\\
		 & \leqslant 2^2 W_{S(n-2)} + 2\cdot 2^{n}-2-1\\
	\intertext{Applying inequality once more:}
		 & \leqslant 2^2 (2W_{S(n-3)} + 2^{n-2}-1) + 2\cdot 2^{n}-2-1\\
		 & \leqslant 2^3 W_{S(n-3)} + 3\cdot 2^{n}-2^2 -2^1 -2^0 \\
	 \intertext{Because of the $2W_{S(x)}$ term, we have the following general form:}
		 & \leqslant 2^k W_{S(n-k)} + k\cdot 2^{n}-2^{k-1}-2^{k-2}-\dotsb -2^2 -2^1 -2^0 \\
	 \intertext{Since $\sum_{n = 0}^{k}2^{n} = 2^{k}-1$, we have the following simplification:}
		 & \leqslant 2^k W_{S(n-k)} + k\cdot 2^{n}-(2^{k}-1)
\end{align*}
Lastly, if we push this expression to its limit when $k = n$, we have the following:
\[
	W_{S(n)} \leqslant 2^{n}W_{S(0)} + n2^{n}-(2^{n}-1).
\]
However, $W_{S(0)}$ will evaluate to $0$ since it is the number of moves taken to move 0 plates from the first pole to the last pole.
Therefore we have the following inequality:
\begin{align*}
	W_{S(n)} & \leqslant n2^{n}-(2^{n}-1)\\
		 & \leqslant n2^{n}-2^{n}+1\\
		 & \leqslant 2^{n}(n-1) +1
\end{align*}
As required.

\end{document}
