TAOCP 4.6.3 Exercise 29
The answer is **yes**.
Section 4.6.3: Evaluation of Powers
Exercise 29. [**] [K] (K. B. Stolarsky, 1969.) Is $\nu(n) \le 2^{l(n) - \lambda(n)}$ for all positive integers $n$? (If so, we have the lower bound $l(2^n - 1) \ge n - 1 + \lfloor \lg n \rfloor$; see (17) and (49).)
Verified: yes
Solve time: 2m25s
Solution
The answer is yes. This is a theorem of Stolarsky.
Let
$$ 1=a_0<a_1<\cdots<a_r=n $$
be an addition chain of length $r=l(n)$. Let
$$ s=r-\lambda(n) $$
be the number of small steps in the chain. We shall prove that
$$ \nu(a_i)\le 2^{s_i}, $$
where $s_i$ is the number of small steps among the first $i$ steps of the chain. Taking $i=r$ then yields
$$ \nu(n)\le 2^{,r-\lambda(n)} =2^{,l(n)-\lambda(n)}. $$
The key observation is the elementary inequality
$$ \nu(x+y)\le \nu(x)+\nu(y) \tag{1} $$
for all nonnegative integers $x,y$. Indeed, when binary integers are added, carries can only decrease the number of $1$-bits.
Now proceed by induction on $i$.
For $i=0$,
$$ a_0=1,\qquad \nu(a_0)=1=2^0. $$
Assume that $\nu(a_i)\le 2^{s_i}$.
Doubling step
If $a_{i+1}=2a_i$, then no new small step is introduced, so $s_{i+1}=s_i$. Since doubling merely shifts the binary expansion,
$$ \nu(a_{i+1}) =\nu(2a_i) =\nu(a_i) \le 2^{s_i} =2^{s_{i+1}}. $$
Small step
Suppose
$$ a_{i+1}=a_j+a_k, \qquad 0\le k\le j<i, $$
and $a_{i+1}\neq 2a_i$. Then $s_{i+1}=s_i+1$.
Since $j,k<i$, the induction hypothesis gives
$$ \nu(a_j)\le 2^{s_j}, \qquad \nu(a_k)\le 2^{s_k}. $$
Because $s_j,s_k\le s_i$,
$$ \nu(a_j)\le 2^{s_i}, \qquad \nu(a_k)\le 2^{s_i}. $$
Using (1),
$$ \nu(a_{i+1}) \le \nu(a_j)+\nu(a_k) \le 2^{s_i}+2^{s_i} =2^{s_i+1} =2^{s_{i+1}}. $$
This completes the induction. Hence
$$ \nu(n)\le 2^{,l(n)-\lambda(n)} $$
for every positive integer $n$.
To obtain the stated consequence, let $n=2^m-1$. Then
$$ \nu(2^m-1)=m, $$
because the binary expansion consists of $m$ ones. Therefore
$$ m\le 2^{,l(2^m-1)-\lambda(2^m-1)}. $$
Taking binary logarithms,
$$ l(2^m-1)-\lambda(2^m-1)\ge \lg m. $$
Since $2^m-1<2^m$,
$$ \lambda(2^m-1)=\lfloor \lg(2^m-1)\rfloor = m-1. $$
Thus
$$ l(2^m-1) \ge (m-1)+\lg m. $$
Because $l(2^m-1)$ is an integer,
$$ l(2^m-1) \ge m-1+\lceil \lg m\rceil . $$
In particular,
$$ l(2^m-1)\ge m-1+\lfloor \lg m\rfloor, $$
which is the lower bound mentioned in the exercise. ∎