$1000$-digit Fibonacci Number

The Fibonacci sequence is defined by the recurrence relation:
$F_n = F_{n – 1} + F_{n – 2}$, where $F_1 = 1$ and $F_2 = 1$.
Hence the first $12$ terms will be:
\begin{align}
F_1 &= 1\\
F_2 &= 1\\
F_3 &= 2\\
F_4 &= 3\\
F_5 &= 5\\
F_6 &= 8\\
F_7 &= 13\\
F_8 &= 21\\
F_9 &= 34\\
F_{10} &= 55\\
F_{11} &= 89\\
F_{12} &= 144
\end{align}
The $12$th term, $F_{12}$, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain $1000$ digits?

The Fibonacci sequence grows exponentially, so we can use the formula for the Fibonacci sequence derived from the roots of its characteristic equation to estimate the index of the first Fibonacci number with 1000 digits.

The Fibonacci sequence is defined by the recurrence relation:
F(n) = F(n-1) + F(n-2)
with F(1) = F(2) = 1.

From Binet’s formula, Fibonacci numbers have an approximate expression, which for large n reads as follows:

F(n) ~= (phi^n) / sqrt(5), where ~= represents approximation and phi = (1 + sqrt(5)) / 2 is the so-called golden ratio, roughly equal to 1.61803.

We want the index of the first Fibonacci number which contains 1000 digits, which implies that we search for the smallest n such that:

F(n) >= 10^(1000 – 1)

Substituting F(n) from above and rearranging:

(phi^n) / sqrt(5) >= 10^(1000 – 1)

n * log10(phi) – log10(sqrt(5)) >= 1000 – 1

We should round up this result, since we need the smallest integer index greater than the value computed.

Noting that log10(phi) is approximately 0.208987 and log10(sqrt(5)) is approximately 0.349485, we substitute these values and solve for n.

n * 0.208987 – 0.349485 >= 999
n >= (999 + 0.349485) / 0.208987

Computing this and rounding up to the next integer gives n = 4782.

Therefore, the index of the first term in the Fibonacci sequence to contain 1000 digits is 4782.

More Answers: