TAOCP 1.2.8 Exercise 2

Exercise 2. [20] In view of Eq. (15), what is the approximate value of $F_{1000}$? (Use logarithms found in Appendix A.)

Verified: no
Solve time: -

Solution

Equation (15) gives

$$ F_n = \frac{\phi^n}{\sqrt{5}} \text{ rounded to the nearest integer,} \qquad \phi = \frac{1+\sqrt{5}}{2}. $$

We want $F_{1000}$. First compute

$$ \log_{10} F_{1000} \approx \log_{10} \frac{\phi^{1000}}{\sqrt{5}} = 1000 \log_{10} \phi - \frac{1}{2} \log_{10} 5. $$

By Appendix A, $\log_{10} \phi \approx 0.20898764$ and $\log_{10} 5 \approx 0.69897000$. Therefore

$$ 1000 \log_{10} \phi \approx 1000 \times 0.20898764 = 208.98764, $$

and

$$ \frac{1}{2} \log_{10} 5 \approx 0.349485. $$

Subtracting,

$$ \log_{10} F_{1000} \approx 208.98764 - 0.349485 = 208.638155. $$

Thus $F_{1000} \approx 10^{208.638155}$. To convert this to a decimal integer, write

$$ 10^{208.638155} = 10^{0.638155} \cdot 10^{208}. $$

Compute $10^{0.638155}$: using logarithm tables or a calculator,

$$ 10^{0.638155} \approx 4.3529. $$

Hence

$$ F_{1000} \approx 4.3529 \times 10^{208}. $$

Rounding to the nearest integer gives the first few digits as $43529$ followed by $203$ additional digits, for a total of $209$ digits. Therefore

$$ \boxed{F_{1000} \approx 4.3529 \times 10^{208}}. $$

This completes the solution.

∎