Let $\ell(n)$ be the smallest number of multiplications needed to compute $a^n$ for any integer $a$. Here, a multiplication is $a_i := a_j \cdot a_k$ for $j, k < i$ and $a_0 := a$, e.g. $\ell(8) = 3$. I want to show the following inequality:
$\lambda(n) \leq \ell(n) \leq \lambda(n) + v(n) + 1,$
where $\lambda(n)$ is one less than the number of significant bits of $n$ in the binary representation and $v(n)$ is the number of $1$s in the binary representation of $n$.
I tried to prove this inequality using induction and the upper bound for $\ell(n)$ is quite easy to show, however I don't see how I can prove the lower bound. The only thing about $\ell(n+1)$ I know is that it is less or equal to $\ell(n) + 1$. But if we for example look at $n=7$, we see that $\ell(n+1) < \ell(n)$, so $\ell(n)$ is not monotonically increasing... Can anyone give me a hint how to show the lower bound or how $\ell(n)$ is bounded?
Thanks for any help in advance.