TAOCP 6.4 Exercise 50
By equation (42), the quantity $Q_o(M,N)$ satisfies Q_o(M,N) = 1 + \frac{N}{M} Q_o(M,N-1).
Exercise 50. [M20] [M20] Show that Qi(M, N) = M, (M, N-, -1)Qo(M, N), in the notation of (42). [Hint: Prove first that Qi(M,N) = (N + 1)Qo(M, N), NQo(M, N-1).]
Verified: yes
Solve time: 1m27s
Solution
By equation (42), the quantity $Q_o(M,N)$ satisfies
$$ Q_o(M,N) = 1 + \frac{N}{M} Q_o(M,N-1). $$
Solving this for $Q_o(M,N-1)$ gives
$$ Q_o(M,N-1) = \frac{M}{N}\bigl(Q_o(M,N) - 1\bigr). $$
Start from the identity given in the hint,
$$ Q_i(M,N) = (N+1)Q_o(M,N) - NQ_o(M,N-1). $$
Substituting the expression for $Q_o(M,N-1)$ yields
$$ Q_i(M,N) = (N+1)Q_o(M,N) - N \cdot \frac{M}{N}\bigl(Q_o(M,N) - 1\bigr). $$
Simplifying the second term,
$$ Q_i(M,N) = (N+1)Q_o(M,N) - M\bigl(Q_o(M,N) - 1\bigr). $$
Expanding,
$$ Q_i(M,N) = (N+1)Q_o(M,N) - MQ_o(M,N) + M. $$
Collecting terms in $Q_o(M,N)$,
$$ Q_i(M,N) = \bigl(N+1-M\bigr)Q_o(M,N) + M. $$
Rewriting the coefficient,
$$ N+1-M = -(M-N-1), $$
so
$$ Q_i(M,N) = M - (M-N-1)Q_o(M,N). $$
This completes the proof. ∎