How to improve this bound?

Question

As everyone reading this should very well know, $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n - 2} + F_{n - 1}$ for all integers $n > 1$. The choice of uppercase F for the Fibonacci numbers seems to be fairly standard.

I'm not sure what the standard notation is for the binary weight function, so I'll use $wt_2(n)$. For example, $wt_2(14) = 3$ since $14$ in binary is $1110$ and that's three $1$s; $wt_2(15) = 4$ since $15$ in binary is $1111$ and that's three $1$s. For now, I'm unconcerned about negative integers.

Now, what is $wt_2(F_n)$? It's at most $wt_2(F_{n - 2}) + wt_2(F_{n - 1})$. But, except for $F_3 = 2$, that seems like overkill. Can this be improved for $n > 3$?

EDIT: As Robert pointed out, $n = 10$ is another example. But I've gone up to $n = 2500$ and it looks to me like $wt_2(F_{n - 2}) + wt_2(F_{n - 1})$ is a vast overestimate for $wt_2(F_n)$.

Answer 1

Well using induction on $n$, it can be shown that
$$F_n\lt 2^n$$ So the weight of $F_n$ is less than $n$.

Answer 2

By Binet’s formula, $F_n=\tfrac 1{\sqrt{5}}(\varphi^n-(-\varphi)^{-n})$ for each $n$, where $\varphi=\frac {\sqrt{5}+1}2$ is the golden ratio. This fact provides an upper bound for $\operatorname{wt}_2 F_n$ about $n\log_2\varphi\simeq 0.694 n.$ My computer calculations for small values of $n$ and a guess that approximately a half of binary digits of $F_n$ are $1$’s suggest a conjecture that $$\operatorname{wt}_2 F_n=n\frac {\log_2\varphi}2+o(n).$$

Using your data, you can try to look what happens up to $n=2500$.