There is a standard problem to show that the distribution of leading digits of $2^n$ is that the digit $k$ occurs with the frequency $\log_{10}(k+1)-\log_{10}(k)$. (This easily generalises to other bases --- though base 2 is rather pointless!)

Since Fibonacci is also ``exponential except for an error term''. Is this true for that as well --- or does the error term make it fail?

  • 1
    $\begingroup$ The error term is $o(1)$, so whatever you have for $2^n$ should also work for the Fibonacci sequence. $\endgroup$
    – GH from MO
    Feb 6 '12 at 17:48
  • 4
    $\begingroup$ How could the error term possibly affect the distribution of the leading digit? $\endgroup$ Feb 6 '12 at 17:54
  • $\begingroup$ The phrasing with the emphasize on the error term is perhaps confusing, but then I do not (fully) understand the remark of GH as the 'base' is not 2 for Fibinacci. Okay, in the end 'the reason' is 'the same'; I will expand my answer a bit. $\endgroup$
    – user9072
    Feb 6 '12 at 18:07

Yes, this is true. The sequence of Fibonacci numbers is known to satisfy Benford's Law. See the wikipedia page of Benford's Law for details (in particular see Distributions that satisfy Benford's law exactly).

More specifically, L. C. Washington showed in Benford's Law for Fibonacci and Lucas numbers, Fib. Quaterly 1981 that both Fibonacci and Lucas numbers satisfy the extended Benford's Law (that is arbitrary base as mentioned in the question).
The key part of the proof is to show that $n \log \phi$ is uniformly distributed modulo $1$ where $\phi$ is the Golden Ratio (the base of the logarithm being the one for which the law should be established). This is achieved using Weyl's equidistribution theorem.


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.