Пусть $u_n$ — последовательность Фибоначчи: $u_0=1$, $u_1=1$,
$$
u_{n+1}=u_n+u_{n-1}.\tag1
$$
Нам понадобится следующая простая оценка отношения $r_n=\dfrac{u_{n+1}}{u_n}$ соседних чисел Фибоначчи: начиная с $\dfrac{u_3}{u_2}=\dfrac{3}{2}$, отношение $r_n$ не меньше $\dfrac{3}{2}=1{,}5$ и не больше $\dfrac{5}{3}=1{,}66\ldots\lt 1{,}7$.
Её легко доказать методом математической индукции. В силу (1)
$$
r_n=\dfrac{u_{n+1}}{u_n}=1+\dfrac{u_{n-1}}{u_n}=1+\dfrac{1}{r_{n-1}}.
$$
Поэтому, если
$$
\dfrac32\le r_{n-1}\le\dfrac53,\tag2
$$
т. е. $\dfrac23\ge\dfrac1{r_{n-1}}\ge\dfrac35$, то $r_n$ оценивается сверху числом $1+\dfrac23=\dfrac53$, а снизу — числом $1+\dfrac35=\dfrac85\gt\dfrac32$. А поскольку оценка (2) верна для $n=3$, она верна и для всех $n\ge3$.
Пусть $u_k$ — наименьшее $m$-значное число Фибоначчи, $m\ge2$. Тогда $u_k\ge10^{m-1}$, $$
\begin{align*}
u_{k+1}&\ge1{,}5u_k,\\
u_{k+2}&=u_{k+1}+u_k\ge2{,}5u_k,\\
u_{k+3}&\ge(2{,}5+1{,}5)u_k=4u_k,\\
u_{k+4}&\ge(4+2{,}5)u_k=6{,}5u_k,
\end{align*}
$$
и потому $u_{k+5}\ge10{,}5u_k\gt10^m$ — уже не менее, чем $(m+1)$-значное число. Таким образом, $m$-значных чисел Фибоначчи не более 5.
С другой стороны, $u_{k-1}\lt10^{m-1}$, $u_k\lt1{,}7u_{k-1}$ и аналогично предыдущему мы получим, что $u_{k+3}\lt7{,}1u_{k-1}\lt10^m$. Следовательно, $m$-значных чисел Фибоначчи не менее 4.
Можно решить эту задачу иначе, воспользовавшись явной формулой для чисел Фибоначчи:
$$
u_n=\dfrac{\tau^{n+1}-\left(-\dfrac1\tau\right)^{n+1}}{\sqrt5},\quad\text{где}~\tau=\dfrac{1+\sqrt5}2.
$$
