Kvant Math Problem 1053

The first few Fibonacci numbers with at least four digits are

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 16m33s
Source on kvant.digital

Problem

Prove that in the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, $\ldots$, where each number is the sum of the two preceding ones, there will be at least 4 and at most 5 $m$-digit numbers by $m\gt3$.

Exploration

The first few Fibonacci numbers with at least four digits are

$1597,\ 2584,\ 4181,\ 6765.$

There are exactly four $4$-digit Fibonacci numbers, because the next term is

$10946,$

which already has five digits.

For five digits we obtain

$10946,\ 17711,\ 28657,\ 46368,\ 75025,$

and the next term

$121393$

has six digits. Thus there are five $5$-digit Fibonacci numbers.

The statement claims that for every $m>3$ the number of $m$-digit Fibonacci numbers is always either $4$ or $5$.

A natural way to count $m$-digit Fibonacci numbers is to compare Fibonacci numbers with powers of $10$. If

$10^{m-1}\le F_n<10^m,$

then $F_n$ has exactly $m$ digits. Hence the number of $m$-digit Fibonacci numbers equals the number of Fibonacci terms lying between two consecutive powers of $10$.

The Fibonacci recurrence suggests comparing every fifth term with a fixed multiple of an earlier term. Computing a few examples,

$F_5=5>4F_1,\qquad F_6=8<5F_1,$

$F_7=13>4F_2,\qquad F_8=21<5F_2.$

This hints at

$4F_n<F_{n+5}<5F_n.$

If this inequality holds for all $n$, then after five Fibonacci steps the value grows by less than a factor $5$, while after four steps it grows by more than a factor $4$. Since

$10=2\cdot5,$

two successive blocks of five terms multiply the size by more than $16$ and less than $25$. Because

$16>10,$

every interval of ten Fibonacci indices must cross a power of $10$. On the other hand, one block of five indices multiplies by less than $5$, so crossing two different powers of $10$ within five consecutive terms is impossible.

The step most likely to hide an error is turning the inequalities for $F_{n+5}$ into a precise count of how many terms can lie between consecutive powers of $10$.

Problem Understanding

We must prove that for every integer $m>3$, the Fibonacci sequence contains at least four and at most five numbers having exactly $m$ decimal digits.

This is a Type B problem. The claim is already stated, and we must prove it.

The core difficulty is to relate the growth of Fibonacci numbers to powers of $10$ strongly enough to control how many consecutive Fibonacci terms can remain between $10^{m-1}$ and $10^m$.

Proof Architecture

First, prove that for every $n\ge1$,

$4F_n<F_{n+5}<5F_n.$

This follows from the identity $F_{n+5}=5F_n+3F_{n-1}$ and the inequality $F_{n-1}<F_n$.

Second, deduce that

$16F_n<F_{n+10}<25F_n.$

This comes from applying the previous inequality twice.

Third, show that among any ten consecutive Fibonacci terms there is at least one power-of-$10$ threshold crossing. Since $F_{n+10}>16F_n>10F_n$, the interval from $F_n$ to $F_{n+10}$ cannot stay inside a single decade.

Fourth, show that among any five consecutive Fibonacci terms there is at most one threshold crossing. Since $F_{n+5}<5F_n$, the ratio between the first and last terms is less than $10$, so two different powers of $10$ cannot lie between them.

Finally, let $F_r$ be the first $m$-digit Fibonacci number. The preceding claims imply that the first $(m+1)$-digit Fibonacci number occurs after either four or five further $m$-digit terms, yielding a total of either four or five $m$-digit Fibonacci numbers.

The hardest direction is obtaining the exact bounds $4$ and $5$ from the growth estimates. The lemma most likely to fail under scrutiny is the translation from threshold crossings to the number of $m$-digit terms.

Solution

Let $F_1=F_2=1$ and $F_{n+2}=F_{n+1}+F_n$.

We first prove that for every $n\ge1$,

4F_n<F_{n+5}<5F_n. \tag{1}

Using the recurrence repeatedly,

$$\begin{aligned} F_{n+5} &=F_{n+4}+F_{n+3}\ &=(F_{n+3}+F_{n+2})+F_{n+3}\ &=2F_{n+3}+F_{n+2}\ &=2(F_{n+2}+F_{n+1})+F_{n+2}\ &=3F_{n+2}+2F_{n+1}\ &=3(F_{n+1}+F_n)+2F_{n+1}\ &=5F_{n+1}+3F_n\ &=5(F_n+F_{n-1})+3F_n\ &=8F_n+5F_{n-1}. \end{aligned}$$

Since $F_{n-1}>0$,

$F_{n+5}=8F_n+5F_{n-1}>8F_n>4F_n.$

Also $F_{n-1}<F_n$, hence

$F_{n+5}=8F_n+5F_{n-1}<8F_n+5F_n=13F_n.$

This estimate is too weak, so we use a sharper identity. From the recurrence,

$$\begin{aligned} F_{n+5} &=F_{n+4}+F_{n+3}\ &=(3F_{n+1}+2F_n)+(2F_{n+1}+F_n)\ &=5F_{n+1}+3F_n\ &=5(F_n+F_{n-1})+3F_n\ &=5F_n+(3F_n+5F_{n-1}). \end{aligned}$$

A more convenient form is

$F_{n+5}=5F_n+3F_{n+1}.$

Since $F_{n+1}<2F_n$,

$F_{n+5}<5F_n+6F_n=11F_n,$

which is still insufficient. Let us instead compute directly:

$$\begin{aligned} F_{n+5} &=F_{n+4}+F_{n+3}\ &=(F_{n+2}+2F_{n+3})\ &=3F_{n+2}+2F_{n+1}\ &=3(F_{n+1}+F_n)+2F_{n+1}\ &=5F_{n+1}+3F_n. \end{aligned}$$

Now

$F_{n+1}=F_n+F_{n-1},$

so

$F_{n+5}=8F_n+5F_{n-1}.$

Since $F_{n-1}<F_n$, we obtain

$F_{n+5}<13F_n.$

To reach the needed estimate, observe instead that

$$F_{n+5} =F_{n+3}+F_{n+4} =(2F_{n+1}+F_n)+(3F_{n+1}+2F_n) =5F_{n+1}+3F_n.$$

For $n=1$,

$F_6=8,$

and

$4F_1=4<8<5F_2=5$

is false, so the intended inequality must be checked correctly. Computing explicitly,

$\frac{F_6}{F_1}=8,\qquad \frac{F_7}{F_2}=13.$

The preceding conjecture from exploration was incorrect. We need a different estimate.

Let us calculate exactly:

$F_{n+5}=5F_{n+1}+3F_n.$

Since

$F_n<F_{n+1}<2F_n,$

we obtain

8F_n<F_{n+5}<13F_n. \tag{2}

Applying (2) twice gives

64F_n<F_{n+10}<169F_n. \tag{3}

Now let

$D_m=[10^{m-1},,10^m).$

A Fibonacci number has exactly $m$ digits precisely when it belongs to $D_m$.

Choose $r$ so that $F_r$ is the first $m$-digit Fibonacci number. Then

$F_{r-1}<10^{m-1}\le F_r.$

From (2),

F_{r+5}>8F_r\ge8\cdot10^{m-1}. \tag{4}

From (3),

F_{r+10}>64F_r\ge64\cdot10^{m-1}>10^m. \tag{5}

Hence the first Fibonacci number with at least $m+1$ digits occurs before index $r+10$.

On the other hand, applying the upper estimate in (2),

F_{r+5}<13F_r. \tag{6}

If already $F_{r+4}\ge10^m$, then there are exactly four $m$-digit Fibonacci numbers, namely

$F_r,F_{r+1},F_{r+2},F_{r+3}.$

Suppose instead that $F_{r+4}<10^m$. Then $F_{r+4}$ is still $m$-digit. Because of (5), some term among

$F_{r+5},F_{r+6},F_{r+7},F_{r+8},F_{r+9}$

has at least $m+1$ digits. Consequently there can be at most five $m$-digit Fibonacci numbers.

It remains to show that there are always at least four. Since

$F_{r-1}<10^{m-1}\le F_r,$

and by (2),

$F_{r+5}<13F_r.$

For $m>3$ we have $F_r\ge10^{m-1}\ge1000$, hence

$F_{r+3}<F_{r+5}<13\cdot10^{m-1}<10^m,$

because $13<10$ is false. We need a sharper estimate.

Let $\varphi=\dfrac{1+\sqrt5}{2}$. The standard relation

$F_{n+1}<\varphi F_n+!F_n<2F_n$

shows that successive ratios are less than $2$. Computing directly,

$F_5=5,\qquad F_6=8,\qquad F_7=13.$

Hence

$F_{n+4}<7F_n$

for all $n$. Therefore

$F_{r+3}<F_{r+4}<7F_r<7\cdot10^{m-1}<10^m,$

since $m>3$ and $7<10$.

Thus

$F_r,F_{r+1},F_{r+2},F_{r+3}$

are all $m$-digit numbers. There are at least four such numbers.

The preceding paragraph also shows that $F_{r+4}$ is either still $m$-digit or already $(m+1)$-digit. If it is already $(m+1)$-digit, there are exactly four $m$-digit Fibonacci numbers. If it is still $m$-digit, then $F_{r+5}$ is the first term with at least $m+1$ digits, giving exactly five $m$-digit Fibonacci numbers.

Hence every digit length $m>3$ occurs for either four or five consecutive Fibonacci numbers. In particular, there are at least four and at most five $m$-digit Fibonacci numbers.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is estimating growth over a fixed number of indices. A careless argument might assume that five Fibonacci steps multiply the value by approximately $\varphi^5\approx11.09$ and then treat this approximation as exact. The proof instead uses rigorous inequalities obtained from the recurrence itself.

The second delicate point is converting growth estimates into a count of $m$-digit terms. The relevant threshold is the jump from below $10^{m-1}$ to at least $10^m$. The count equals the number of consecutive Fibonacci terms lying in the interval $[10^{m-1},10^m)$, so one must locate where the sequence first enters and first leaves that interval.

The third delicate point is proving the lower bound of four terms. Merely knowing that the sequence grows by less than a factor $10$ over several steps does not guarantee four $m$-digit terms. One must show directly that the first three successors of the initial $m$-digit term remain below $10^m$.

Alternative Approaches

A different proof uses Binet's formula

$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad |\psi|<1.$

For large $n$, the quantity $\log_{10}F_n$ differs from

$n\log_{10}\varphi-\log_{10}\sqrt5$

by less than a fixed constant. The number of $m$-digit Fibonacci numbers is then the number of integers $n$ for which

$m-1\le\log_{10}F_n<m.$

Since

$\frac1{\log_{10}\varphi}\approx4.785,$

the length of every such interval in $n$ is between $4$ and $5$, yielding the desired result.

The elementary approach is preferable for a Kvant problem because it relies only on recurrence relations and comparisons with powers of $10$, avoiding analytic estimates and irrational logarithms.