# How to improve this bound?

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)$$.

• for weight of 15 you wrote "and that's three ones" but correctly said weight is 4. – coffeemath Apr 6 at 22:33
• Are you interested in other upper bounds (not using weights)? – coffeemath Apr 6 at 22:35
• @coffeemath In your shoes I would have gone ahead and put in that correction, since it seems to be that David copied and pasted and neglected to make all the necessary changes. What I would get on his case about is $F_{10} = 55$, 0b110111, which follows 0b10101 and 0b100010. – Robert Soupe Apr 7 at 2:01
• @coffeemath I'm gonna have to read up on weights, I don't even know what the term means in this context. – David R. Apr 11 at 20:53

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$$.
• Indeed, this looks like a good bound (and with some further effort might be improved to something like $n-c$ for some constant $c$), so I don't understand why the OP offered a bounty instead of accepting this answer. – Alex M. Apr 29 at 7:25
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$$.
• I don't have the time to check the details, but I think your conjecture can be proved using the formula $F_{n+d}=F_{d-1}F_{n-d+1}+F_{d-2}F_{n-d}$. You deduce an upper and a lower bound for $\frac{F_{n+d}}{F_n}$, and when $\frac{F_{n+d}}{F_n}-\phi^d$ is small, $\frac{wt_2(F_n)}{n}-\frac{\log_2(\phi)}{2}$ should be small also. – Ewan Delanoy Apr 30 at 16:38
• better than $o(n)$ I conjecture $O(\sqrt{n})$. – Somos May 3 at 12:40