MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
The error term is $o(1)$, so whatever you have for $2^n$ should also work for the Fibonacci sequence. – GH from MO Feb 6 '12 at 17:48
How could the error term possibly affect the distribution of the leading digit? – Qiaochu Yuan Feb 6 '12 at 17:54
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. – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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