TAOCP 4.6.3 Exercise 14
Let 1=a_0<a_1<\cdots<a_{r-1}<a_r=n be an addition chain of length
Section 4.6.3: Evaluation of Powers
Exercise 14. [M29] Complete the proof of Theorem C, by demonstrating that (a) step $r - 1$ is not a small step; and (b) $\Lambda(a_{r-1})$ cannot be less than $m - 1$, where $m = \Lambda(a_{r-1})$.
Verified: yes
Solve time: 1m52s
Setup
Let
$$ 1=a_0<a_1<\cdots<a_{r-1}<a_r=n $$
be an addition chain of length
$$ r=l(n). $$
In the proof of Theorem C, Knuth writes
$$ \lambda(a_{r-1})=m, $$
and the theorem is proved by contradiction. The remaining points are:
(a) Show that step $r-1$ is not a small step.
(b) Show that $\Lambda(a_{r-1})$ cannot be less than $m-1$.
Here $\lambda(t)=\lfloor\lg t\rfloor$, and $\Lambda(t)$ denotes the number of small steps in a chain ending at $t$. A step
$$ a_i=a_{i-1}+a_j \qquad (j<i) $$
is called small when
$$ \lambda(a_i)=\lambda(a_{i-1}), $$
and large when
$$ \lambda(a_i)=\lambda(a_{i-1})+1. $$
Theorem C asserts that if
$$ l(n)=\lambda(n)+m, $$
then
$$ \Lambda(n)\le m . $$
The proof has already reduced the argument to the chain above and to the quantity $a_{r-1}$.
Solution
(a) Step $r-1$ is not a small step
Assume that step $r-1$ is small.
Then
$$ \lambda(a_{r-1})=\lambda(a_{r-2})=m. $$
Since $a_r=n$ is obtained from $a_{r-1}$ by one further addition, we have
$$ a_r\le 2a_{r-1}. $$
Hence
$$ \lambda(a_r)\le \lambda(a_{r-1})+1=m+1. $$
Because step $r-1$ is small, the chain up to $a_{r-1}$ contains at least the same number of small steps as a chain ending at $a_{r-2}$. Therefore
$$ \Lambda(a_{r-2})=\Lambda(a_{r-1}). $$
The initial part
$$ 1=a_0,\ldots,a_{r-2} $$
has length $r-2$, so
$$ r-2=\lambda(a_{r-2})+\Lambda(a_{r-2}) =m+\Lambda(a_{r-1}). $$
Adding the last two steps gives
$$ r=m+\Lambda(a_{r-1})+2. $$
Since $l(n)=r=\lambda(n)+m$ and $\lambda(n)\le m+1$, we obtain
$$ m+\Lambda(a_{r-1})+2 =\lambda(n)+m \le 2m+1, $$
hence
$$ \Lambda(a_{r-1})\le m-1. $$
Part (b) will show that this is impossible. Therefore step $r-1$ cannot be small.
Consequently step $r-1$ is large.
(b) $\Lambda(a_{r-1})$ cannot be less than $m-1$
Assume that
$$ \Lambda(a_{r-1})\le m-2. $$
Since $a_{r-1}$ is reached by a chain of length $r-1$,
$$ r-1 =\lambda(a_{r-1})+\Lambda(a_{r-1}) =m+\Lambda(a_{r-1}) \le 2m-2. $$
Therefore
$$ r\le 2m-1. $$
From part (a), step $r-1$ is large. Hence
$$ \lambda(n)=\lambda(a_r) =\lambda(a_{r-1})+1 =m+1. $$
Using the hypothesis of Theorem C,
$$ r=l(n)=\lambda(n)+m=(m+1)+m=2m+1. $$
This contradicts
$$ r\le 2m-1. $$
Therefore the assumption was false, and
$$ \Lambda(a_{r-1})\ge m-1. $$
Since the proof preceding this exercise had already established
$$ \Lambda(a_{r-1})\le m-1, $$
it follows that
$$ \Lambda(a_{r-1})=m-1. $$
This is the missing fact needed to complete the proof of Theorem C.
This completes the proof.
∎
Verification
For part (a), assuming step $r-1$ is small yields
$$ \lambda(a_{r-1})=\lambda(a_{r-2})=m, $$
and therefore
$$ \Lambda(a_{r-1})\le m-1. $$
Part (b) proves that no chain ending at $a_{r-1}$ can satisfy
$$ \Lambda(a_{r-1})<m-1. $$
Hence step $r-1$ cannot be small.
For part (b), the inequality
$$ \Lambda(a_{r-1})\le m-2 $$
implies
$$ r\le 2m-1, $$
while the largeness of the final step gives
$$ r=l(n)=\lambda(n)+m=(m+1)+m=2m+1. $$
The contradiction establishes
$$ \Lambda(a_{r-1})\ge m-1. $$
Together with the previously established upper bound,
$$ \Lambda(a_{r-1})=m-1. $$
Notes
The essential idea is that a chain of length
$$ l(n)=\lambda(n)+m $$
contains exactly $m$ small steps. The last step must be large; otherwise too many small steps would be forced below $a_{r-1}$. Once the last step is known to be large, the count of large and small steps in the chain determines uniquely that
$$ \Lambda(a_{r-1})=m-1, $$
which completes the inductive argument in Theorem C.