TAOCP 4.2.4 Exercise 19
Let \phi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}, so that Binet's formula gives
Section 4.2.4: Distribution of Floating Point Numbers
Exercise 19. [HM25] (R. L. Duncan.) Prove that the leading digits of Fibonacci numbers obey the logarithmic law of fraction parts: $\Pr(10f_{F_n} < r) = \log_{10} r$.
Verified: yes
Solve time: 1m28s
Solution
Let
$$ \phi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}, $$
so that Binet's formula gives
$$ F_n=\frac{\phi^n-\psi^n}{\sqrt5}. $$
Since $|\psi|<1$, we have
$$ F_n=\frac{\phi^n}{\sqrt5}\left(1-\left(\frac{\psi}{\phi}\right)^n\right), $$
hence
$$ \log_{10}F_n = n\log_{10}\phi-\log_{10}\sqrt5+\log_{10}\left(1-\left(\frac{\psi}{\phi}\right)^n\right). $$
Define
$$ \alpha=\log_{10}\phi,\qquad \beta=-\log_{10}\sqrt5, $$
and
$$ \epsilon_n=\log_{10}\left(1-\left(\frac{\psi}{\phi}\right)^n\right). $$
Then
$$ \log_{10}F_n=n\alpha+\beta+\epsilon_n. $$
Since
$$ \left|\frac{\psi}{\phi}\right| = \frac{3-\sqrt5}{2} <1, $$
we have $\epsilon_n\to0$.
The fraction part of $\log_{10}F_n$ determines the leading digits of $F_n$. Indeed,
$$ 10f_{F_n} = 10^{(\log_{10}F_n)\bmod1}. $$
Therefore
$$ 10f_{F_n}<r $$
if and only if
$$ (\log_{10}F_n)\bmod1<\log_{10}r. $$
Thus it suffices to prove that the sequence
$$ (n\alpha+\beta+\epsilon_n)\bmod1 $$
is uniformly distributed modulo $1$.
The number $\alpha=\log_{10}\phi$ is irrational. For if $\alpha=a/b$ were rational, with integers $a,b>0$, then
$$ \phi^b=10^a. $$
The left side is irrational, since $\phi$ is irrational and $b>0$, while the right side is rational. This is impossible.
By Weyl's theorem, the sequence
$$ (n\alpha+\beta)\bmod1 $$
is uniformly distributed modulo $1$ because $\alpha$ is irrational.
Since $\epsilon_n\to0$, the sequences
$$ (n\alpha+\beta)\bmod1 $$
and
$$ (n\alpha+\beta+\epsilon_n)\bmod1 $$
have the same distribution modulo $1$. Hence
$$ (\log_{10}F_n)\bmod1 $$
is uniformly distributed on $[0,1)$.
Therefore, for every $1\le r<10$,
$$ \Pr(10f_{F_n}<r) = \Pr((\log_{10}F_n)\bmod1<\log_{10}r) = \log_{10}r. $$
Consequently the leading digits of the Fibonacci numbers obey the logarithmic law. This completes the proof.
∎