Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What are the first 3 digits of the product of the first 1000 Fibonacci numbers?

Could anyone give me hints on how to start this problem? I haven't done a problem like this before and I am curious on how to approach such a problem.

share|improve this question
    
First three digits from left to right? From right to left? –  Andres Caicedo Jul 1 '13 at 7:13
    
From left to right I believe. –  Ozera Jul 1 '13 at 7:15
2  
What do you mean, you believe? You are the one asking the question. –  Andres Caicedo Jul 1 '13 at 7:16
2  
@Andres: The question What are the first $3$ digits ... numbers. –  Brian M. Scott Jul 1 '13 at 7:26
2  
Brian would be right on "Or perhaps just the one transmitting the question" –  Ozera Jul 1 '13 at 7:28

3 Answers 3

up vote 7 down vote accepted

Binet's formula gives us a useful approximation ($\tau=(1+\sqrt5)/2$) $$ F_n\approx\frac{\tau^n}{\sqrt5}. $$ For example with $n=8$ the r.h.s. is $21.00952$.

We have $F_1F_2\cdots F_7=3120$, so $$ \begin{aligned} \log(\prod_{i=1}^{1000}F_i)&\approx\log(3120)+\sum_{i=8}^{1000}(i\log\tau-\log\sqrt5)\\ &=\log(3120)+500472\log\tau-\frac{993}2\log5\\ &\approx 104248.9178386, \end{aligned} $$ so using the fractional part of that gives $$ 10^{0.9178386}\approx8.27635. $$ Thus the answer is $827$ or something close to it. I skipped the estimation of the error. Note that the error to Binet's formula alternates and tends to zero, so it is not too difficult to estimate it.

share|improve this answer
    
The error in $F_8$ is approximately one part in 2000. Some of that will get cancelled by the error in $F_9$, but this gives us a reason to believe that the answer is correct up to 3 significant digits. –  Jyrki Lahtonen Jul 1 '13 at 9:29

Hint: $F_n$ is very close to $\varphi^n/\sqrt{5}$, where $\varphi = \ldots$. You should be able to use this approximation for $N < n \le 1000$ (for suitable $N$, hopefully not too big), and compute $F_1 \ldots F_N$ exactly. It may be best to work with logarithms rather than with the product directly.

share|improve this answer

Assuming we have agreement that the sequence starts with: {1, 1, 2, 3, 5, 8, 13, ...}, then one can just compute it. Here is the product using Mathematica:

Product[Fibonacci[i], {i, 1, 1000}]

827363170408544049180720689718382309620058799258572848699373843 ... etc etc goes on for a few pages.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.