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$ – Qiaochu Yuan 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.

| cite | improve this answer | |

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.