8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ for weight of 15 you wrote "and that's three ones" but correctly said weight is 4. $\endgroup$ – coffeemath Apr 6 at 22:33
  • $\begingroup$ Are you interested in other upper bounds (not using weights)? $\endgroup$ – coffeemath Apr 6 at 22:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Robert Soupe Apr 7 at 2:01
  • $\begingroup$ @coffeemath I'm gonna have to read up on weights, I don't even know what the term means in this context. $\endgroup$ – David R. Apr 11 at 20:53
9
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Alex M. Apr 29 at 7:25
7
+100
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ewan Delanoy Apr 30 at 16:38
  • 1
    $\begingroup$ better than $o(n)$ I conjecture $O(\sqrt{n})$. $\endgroup$ – Somos May 3 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.