Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

A set of numbers is said to satisfy Benford's law if the leading digit d (d ∈ {1, ..., 9}) occurs with probability,

$$ P(d)=\log_{10}(d+1)-\log_{10}d$$

With Birkhoff's Ergodic Theorem is possible to prove that the sequence $2^n$( for example) satisfies the Benford's law.

The Fibonacci sequence satisfies Berford's law?

share|cite|improve this question
Given that the Fibonacci sequence behaves (asymptotically) like $\varphi^n$, the first digits of which ought to follow the same distribution as $2^n$, I'm going to say the answer is probably yes. – Jonathan Christensen Dec 29 '12 at 15:56
you are right. Indeed every solution of a difference equation satisfies the Benford's law. – user52188 Dec 29 '12 at 16:02
Note that the sequence $10^n$ doesn't satisfy Benford's law. Neither does $\sqrt[3]{10} ^n$. Reasoning is in my answer. – Calvin Lin Dec 29 '12 at 16:10
almost every solution of a difference equation. you are right – user52188 Dec 29 '12 at 16:41
Since the tribonacci sequence is also $T_n \approx Ax_1^n$, then by Calvin Lin's argument, the tribonacci numbers follow Benford's law as well. – Tito Piezas III Feb 26 at 19:36
up vote 5 down vote accepted

Yes.If $x$ is a real value that is not a rational power of 10, then $x^n$ will satisfy Benford's law. To see this, note that $\log x$ is irrational, hence consider $\log x$ looping around the unit circle (fractional part). When $ \log d < \{ n\log x \} < \log (d+1)$, then $x^n$ will have a starting digit of $d$. The sequence $\{ n \log x\}$ is uniformly dense on the unit circle, hence with probability $\log (d+1) - \log d$, $x^n$ will have a starting digit of $d$.

To apply this to the Fibonacci sequence, note that $F_n = A \phi^n + B \phi^{-n}$ and $\phi^{-1}< 1$ hence 'can be ignored'. So $\{ \log F_n \} \approx \{ \log A + n \log \phi \} $, and we have the result as needed.

The reason why we need $x$ to not be a rational power of 10, is so that $\log x$ is not a rational number. If it was, then $n \log x$ will be fixed points around the unit circle, and the starting digits will be extremely fixed. Whereas, when $\log x$ is irrational, it is standard to show that $\log x$ loops around the circle, doesn't return to the starting point, is periodic, hence has uniform density.

share|cite|improve this answer
how do you prove that nlogx is uniformly dense? And is intuive that we can ignore that term, but is not clear to me. – user52188 Dec 29 '12 at 16:53
I know prove that using uniquiness ergodic of roation logx( logx is irrational). Do you proved it using another way? – user52188 Dec 29 '12 at 17:00
The reason why we can ignore the term, is because with $\phi ^{-1} < 1$, then $B\phi^{-n}$ is eventually going to be $<1$ regardless of what $B$ is. (This affects the last digit, and has negligible effect on the first digit, esp with $n>>1000$.) And so the first digit of the Fibonacci number, is going to be equal to the first digit of the irrational number $A \phi^n$ (except possibly in the case when it comes really close to 999999999....) – Calvin Lin Dec 29 '12 at 17:05
While the fact that the irrational rotation of the circle is ergodic is a classical result of ergodic theory, this result actually predates ergodic theory. Take any irrational number, let the fractional part be $\theta$, consider $N = \lfloor \frac {1}{\theta} \rfloor$, look at the values $\{ \theta, 2 \theta, \ldots, N \theta \}$, compare them with the values $\{ (N+1) \theta, (N+2) \theta, \ldots, 2N \theta \}$, which is a rotation by $ 1 - N \theta$ (which is less than $\theta$ by construction). This should be sufficient for you to proceed. – Calvin Lin Dec 29 '12 at 17:12

Your Answer


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