These are some of the notes to help understand the chapter. It fills in some of the gaps I had while studying. It does not provide a summary of any kind. It shows various inductive proofs, follows algebraic steps in a verbose way and points out some subtlties along the way. There’s also a PDF.

Tower of Hanoi

• We hope to find the following by playing with the problem:

  \[\begin{equation*} T_n \leq 2 T_{n-1} + 1 \quad \text{for $n > 0$.} \end{equation*}\]

• We must move \(n-1\) disks before being able to move \(n^{th}\) disk

  \[\begin{equation*} \therefore T_n \geq 2 T_{n-1} + 1 \quad \text{for $n > 0$.} \end{equation*}\]

• By looking at many cases \(n\), we might guess at closed-form:

  \[\begin{equation}\label{hanoiclosed} T_n = 2^n - 1\text{,} \quad \text{for $n \geq 0$.} \end{equation}\]

Proof of closed-form

We proceed using induction.

Base Case: \(n=0\). The equation is simply

\[\begin{align*} n & = 0 \\ \therefore T_0 & = 2^0 - 1 \\ & = 0 \end{align*}\]

Inductive Hypothesis: Assume \(\eqref{hanoiclosed}\) is true for \(n-1\).

\[\begin{align*} T_n & = 2 T_{n-1} + 1 \\ & = 2(2^{n-1} - 1) + 1 \\ & = 2^n - 2 + 1 \\ \therefore T_n & = 2^n - 1 \end{align*}\]

By induction, we have shown that the hypothesis \(\eqref{hanoiclosed}\) holds for \(n+1\).

The recurrence can be solved usuing other methods. The one shown in the chapter (of adding \(1\) to each side etc) leaves some open questions:

• How do we know to add \(1\) on each side?
• How do we know to represent \(U_n = T_{n-1} + 1\)?

Lines in the Plane

Prove that the closed-form for the recurrence is

\[\begin{align}\label{linesclosed} L_n = \frac{n(n-1)}{2} + 1 \text{,} \quad \text{for $n \geq 0$.} \end{align}\]

Base Case: \(n=0\).

\[\begin{align*} L_0 & = \frac{0(0 + 1)}{2} + 1 \\ \therefore L_0 & = 1 \end{align*}\]

Inductive Hypothesis: Assume \(\eqref{linesclosed}\) to be true \(n-1\).

Inductive Step: From recurrence

\[\begin{align*} L_n & = L_{n-1} + n \\ & = \biggl(\frac{n(n-1)}{2} + 1\biggr) + n \\ & = \frac{n^2}{2} - \frac{n}{2} + 1 + n \\ & = \frac{n^2}{2} + \frac{n}{2} + 1 \\ & = \frac{n(n-1)}{2} + 1 \end{align*}\]

Thus, by induction we prove that the hypothesis holds for \(n+1\).

The Josephus Problem

We have to tackle even \(n\) and odd \(n\) separately. We set \(2n\) people in even case because integers multiplied by \(2\) always result in even number. Adding \(1\) to an even integer always results in odd, hence we set \(2n+1\) for the other case. It might take some effort to see that \(J(5 \cdot 2^m) = 2^{m+1} + 1\).

Proving the closed form

We want to prove the following for both — odd and even — cases.

\[\begin{equation}\label{josclosed} J(2^m + \ell) = 2\ell + 1 \end{equation}\]

We proceed with induction on two separate cases.

Base Case: \(n=1\).

\[\begin{equation*} \therefore m = 0 \text{,} \quad \ell = 0\text{.} \end{equation*}\] \[\begin{align*} J(2^m + \ell) & = 2^0 + 0 \\ & = 1 \end{align*}\]

Inductive Step: Suppose that for all \(n\) such that \(n = 2^k + r\), we have \(J(n) = J(2^k + r) = 2r + 1\)

1. Suppose \(m > 0\) and \(n = 2^m + r = 2\ell\). That is, \(n\) is even. From recurrence:

   \[\begin{align*} J(2n) & = 2J(n) - 1 \\ \therefore J(n) & = 2J(\frac{n}{2}) - 1 \\ \therefore J(2^m + \ell) & = 2J\biggl( \frac{2^{m-1}+\ell}{2} \biggr) - 1 \end{align*}\]

   Now, assuming the hypothesis to be true for smaller \(n\):

   \[\begin{align*} J\biggl(\frac{2^{m-1}+\ell}{2}\biggr) & = \frac{2\ell}{2} + 1 \end{align*}\] \[\begin{align*} \therefore J(2^m + \ell) & = 2\biggl(\frac{2\ell}{2} + 1 \biggr) - 1 \\ & = \frac{4\ell}{2} + 2 - 1 \\ \therefore J(2^m + \ell) & = 2\ell + 1 \end{align*}\]

2. Suppose \(m > 0\) and \(n = 2^m + r = 2\ell + 1\). That is, \(n\) is odd. Similar to the even case,

   \[\begin{align*} J(n) & = 2J\biggl(\frac{n}{2} - 1 \biggr) + 1 \end{align*}\]

   Assuming the hypothesis to be true, we get

   \[\begin{align*} J(2^{m-1}+\frac{\ell}{2} - 1) & = 2J(2^{m-1}+\frac{\ell}{2} - 1) + 1 \end{align*}\] \[\begin{align*} \therefore J(n) & = 2 \biggl(\frac{2\ell}{2} + 1 - 1 \biggr) + 1 \\ & = 2\biggl(\frac{2\ell}{2} \biggr) + 1 \\ & = 2\ell + 1 \end{align*}\]

Thus by induction we prove the closed-form for both odd and even cases of \(n\).

Checking where \(J(n)=\frac{n}{2}\) works

\[\begin{align*} J(n) & = \frac{n}{2} \\ \therefore 2\ell + 1 & = \frac{2^m + \ell}{2} \\ \therefore 2^m+\ell & = 2(2\ell + 1) \\ \therefore 2^m & = 4\ell - \ell + 2 \\ \therefore 2^m & = 3\ell + 2 \\ \therefore 3\ell & = 2^m - 2 \\ \therefore \ell & = \frac{1}{3}(2^m - 2) \end{align*}\]

Generalisation of Josephus Problem

We convert constants in the recurrence into variables:

\[\begin{equation} \label{eq:josephus:gen} \begin{split} f(1) & = \alpha\text{,} \\ f(2n) & = 2f(n) + \beta\text{,} \quad \text{for $n \geq 1$;} \\ f(2n + 1) & = 2f(n) + \gamma\text{,} \quad \text{for $n \geq 1$.} \end{split} \end{equation}\]

Equations in (1.12) of the chapter tells us that \(f(n)\) can be written as:

\[\begin{equation} \label{eq:josephus:gen:2} f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma \end{equation}\]

Repertoire Method

We find settings for general parameters (in our case \(\alpha,\beta,\gamma\)) for which we know the solution. This gives us repertoire of special cases that we can solve. Usually, we need as many special cases as there are parameters.

\[\begin{equation} \label{eq:josephus:rep:2} \begin{split} A(n) & = 2^m\text{;} \\ B(n) & = 2^m-1-\ell\text{;} \\ C(n) & = \ell\text{.} \end{split} \end{equation}\]

We proceed with repertoire method.

1. Special case \(\alpha=1\text{,}\beta=\gamma=0\).

   \[\begin{align*} f(n) & = A(n)\alpha + B(n)\beta + C(n)\gamma \end{align*}\] \[\begin{align*} f(1) & = A(1)\cdot 1 + B(1)\cdot 0 + C(1)\cdot 0 \\ \therefore f(1) & = A(1) \\ \therefore A(1) & = 1 \quad \text{from recurrence.} \end{align*}\] \[\begin{align*} f(2n) & = 2A(n)\alpha + B(n)\beta + C(n)\gamma \\ & = 2A(n) + 1 \cdot \beta \\ & = 2A(n) \end{align*}\] \[\begin{align*} f(2n+1) & = 2A(n)\alpha + B(n)\beta + C(n)\gamma \\ & = 2A(n)\cdot 1 + 0 \cdot 0 + 1 \cdot 0 \\ & = 2A(n) \end{align*}\]

   Let’s show \(A(n) = 2^m\). We proceed with proof by induction to show:

   \[\begin{equation} \label{eq:josephus:rep:1} A(2^m+\ell) = 2^m \end{equation}\]

   Base Case: \(n=1\).

   \[\begin{equation*} \therefore m = 0 \text{,} \quad \ell = 0\text{.} \end{equation*}\] \[\begin{align*} A(2^0+0) & = 1 \\ \therefore A(1) & = 1 \end{align*}\]

   Inductive Step: Assume the hypothesis \eqref{eq:josephus:rep:1} to be true for smaller \(n\) like we did for recurrence solution the previous section.

   \[\begin{align*} A(2n) & = 2A(n) \\ \therefore A(n) & = 2A\biggl(\frac{n}{2}\biggr) \\ \therefore A(n) & = 2A\biggl(\frac{2^{m-1}+\ell}{2}\biggr) \end{align*}\]

   Assuming the hypothesis \(\eqref{eq:josephus:rep:1}\) for \(n-1\)

   \[\begin{align*} A(2^{m-1}+\frac{\ell}{2}) & = 2^{m-1} \\ \quad \\ \therefore A(n) & = 2 \cdot 2^{m-1} \\ \therefore A(n) & = 2^m \end{align*}\]

   Similarly,

   \[\begin{align*} A(2n+1) & = 2A(n) \\ \therefore A(n) & = 2A\biggl(\frac{n}{2} - 1\biggr) \\ \therefore A(n) & = 2A\biggl(\frac{2^{m-1}+\ell}{2} - 1\biggr) \\ & = 2 \cdot 2^{m-1} \\ \therefore A(n) & = 2^m \end{align*}\]

   Thus, we show by induction that \(A(n) = 2^m\).

2. Are there any constants (\(\alpha,\beta,\gamma\)) that give the general equation?

   Take \(f(n) = 1\). Since \(f\) always gives \(1\), it is called a “constant function”.

   \[\begin{align*} f(n) & = 1 \\ \therefore \alpha & = 1 \\ \text{And,} \\ 1 & = 2\cdot f(n) + \beta \\ \therefore 1 & = 2 \cdot 1 + \beta \\ \therefore \beta & = -1 \\ \text{And,} \\ 1 & = 2 \cdot f(n) + \gamma \\ \therefore 1 & = 2 + \gamma \\ \therefore \gamma & = -1 \end{align*}\]

   Plugging these values of \(\alpha,\beta,\gamma\) in \(\eqref{eq:josephus:gen:2}\), we get

   \[\begin{align*} f(n) & = A(n)\cdot 1 + B(n)\cdot (-1) + C(n)\cdot (-1) \\ & = A(n) - B(n) - C(n) \\ \quad \\ B(n) & = A(n) - 1 - C(n) \\ \therefore B(n) & = 2^m - 1 - \ell \end{align*}\]

3. Let’s set \(f(n) = n\)

   \[\begin{align*} 1 & = \alpha \\ \text{And,} \\ 2n & = 2f(n) + \beta \\ \therefore 2n & = 2n + \beta \\ \therefore \beta & = 0 \\ \text{And,} \\ 2n + 1 & = 2f(n) + \gamma \\ \therefore 2n + 1 & = 2n + \gamma \\ \therefore \gamma & = 1 \end{align*}\]

   Plugging these values of \(\alpha,\beta,\gamma\) into \(\eqref{eq:josephus:gen:2}\), we get:

   \[\begin{align*} f(n) & = A(n)\alpha + B(n)\beta + C(n)\gamma \\ \therefore n & = A(n)\cdot 1 + B(n)\cdot 0 + C(n)\cdot 1 \\ \therefore n & = A(n) + C(n) \end{align*}\]

With the three cases, we now have

\[\begin{align*} A(n) & = 2^m \\ A(n) - B(n) - C(n) & = 1 \\ A(n) + C(n) & = n \end{align*}\]

Now,

\[\begin{align*} C(n) & = n - A(n) \\ & = n - 2^m \\ \therefore C(n) & = \ell \\ \text{And,} \\ B(n) & = A(n) - 1 - C(n) \\ \therefore B(n) & = 2^m - 1 - \ell \end{align*}\]

Thus we have our hypothesis from \(\eqref{eq:josephus:rep:2}\) proven.

Checking if bit-shift property holds

\[\begin{equation} \label{eq:josephus:radix} f((b_mb_{m-1}\ldots b_1b_0)_2) = (\alpha\beta_{b_{m-1}}\beta_{b_{m-2}}\ldots\beta_{b_1}\beta_{b_0})_2 \end{equation}\]

Equation \(\eqref{eq:josephus:radix}\) is not strictly binary radix. Instead of allowing \(0\) and \(1\) values for \(\beta\), we are allowing any values. This is because our parameters \((\alpha,\beta,\gamma)\) are general and can take any value.

For \(n=100\) in Josephus Problem, we have \(\alpha =1,\beta = -1, \gamma = 1\). Also note that \(\beta_{b_{m-1}}=\beta_{1}=1\), \(\beta_{b_{m-3}}=\beta_{0}=-1\) and so on. The cyclic left bit-shift propery from earlier holds in the generalised form as well:

\[\begin{align*} 100 & = (1100100)_2 \\ 73 & = (1001001)_2 \end{align*}\]