Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
1  
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

1 Answer 1

up vote 3 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|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

 
discard

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