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.

While solving this problem, I discovered that there is a relationship between the Fibonacci sequence and the golden ratio. After I got the correct answer via brute force, I discovered this relationship. One of the posters said this:

The nth Fibonacci number is $[\phi^n / \sqrt{5}\;]$, where the brackets denote "nearest integer".

So we need $\phi^n/\sqrt{5} > 10^{999}$
$n \log(\phi) - \log{5}/2 > 999 \log(10)$
$n \log(\phi) > 999 \log(10) + \log(5)/2$
$n > (999 \log(10) + \log(5) / 2) / \log(\phi)$

A handheld calculator shows the right hand side to be 4781.8593, so 4782 is the first integer n with the desired property.

I can't quite make sense of this. How does the poster know that the $n$-th term is $\phi^n / \sqrt{5}$? Can you also walk me through the operations?

share|improve this question
2  
See en.wikipedia.org/wiki/Fibonacci_numbers section "Closed-form expression" –  nullUser Jul 5 '12 at 20:16
    
Also relevant en.wikipedia.org/wiki/Fibonacci_numbers#Computation_by_rounding –  user17794 Jul 5 '12 at 20:29

2 Answers 2

up vote 5 down vote accepted

Using standard techniques for finding closed-form solutions to recurrences, one can show that $$F_n=\frac{\varphi^n-\hat\varphi^n}{\sqrt5}=\frac{\varphi^n}{\sqrt5}-\frac{\hat\varphi^n}{\sqrt5}\;,\tag{1}$$ where $\varphi=\frac12(1+\sqrt5)$ and $\hat\varphi=\frac12(1-\sqrt5)$. Now $$\left|\frac{\hat\varphi}{\sqrt5}\right|\approx -0.2764<\frac12\;,$$ and $|\hat\varphi|\approx 0.618<1$, so $$\left|\frac{\hat\varphi^n}{\sqrt5}\right|<\frac12$$ for all $n\ge 0$.

Thus, $$\left|F_n-\frac{\varphi^n}{\sqrt5}\right|=\left|\frac{\hat\varphi^n}{\sqrt5}\right|<\frac12$$ for all $n\ge 0$. But we know that $F_n$ is an integer, so $F_n$ is an integer less than half a unit away from $\dfrac{\varphi^n}{\sqrt5}$. That means that $F_n$ is the unique integer closest to $\dfrac{\varphi^n}{\sqrt5}$, so that rounding $\dfrac{\varphi^n}{\sqrt5}$ to the nearest integer gives you $F_n$. In particular,

$$F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor\;,$$ where $\lfloor x\rfloor$ is the largest integer less than or equal to $x$. However, I’m not actually going to use that result; the argument that you posted is slightly defective, and it’s easier to do it right using $(1)$.

A number $m$ has $1000$ digits if and only if $10^{999}\le m<10^{1000}$: $10^{999}$ is the first integer with $1000$ digits, and $10^{1000}-1$ is the last. Thus, we need the smallest $n$ such that $F_n\ge 10^{999}$, or, using $(1)$, the smallest $n$ such that

$$\frac{\varphi^n}{\sqrt5}-\frac{\hat\varphi^n}{\sqrt5}\ge 10^{999}\;.$$

Clearly $n$ is going to be quite large, and we saw earlier that the second term on the left is going to be very small, so to a good first approximation we want the smallest $n$ such that $$\frac{\varphi^n}{\sqrt5}\ge 10^{999}\;;\tag{2}$$ we’ll find that and then come back to make sure that the second term is too small to matter.

$(2)$ is equivalent to $\varphi^n\ge 10^{999}\sqrt5$ and hence, after taking logarithms, to $$n\ln\varphi\ge 999\ln 10+\ln\sqrt5=999\ln 10+\frac12\ln 5\;.\tag{3}$$

Dividing both sides of $(3)$ by $\ln\varphi$, we get

$$n\ge\frac{999\ln 10+\frac12\ln 5}{\ln\varphi}\approx 4781.86\;,$$

where the numerical approximation is taken from a calculator. Clearly the smallest integer $n\ge 4781.86$ is $4782$. A little more work with a calculator shows that $$\log_{10}\frac{\varphi^{4782}}{\sqrt5}\approx 999.0294106732$$ and hence that $$\frac{\varphi^{4782}}{\sqrt5}\approx 1.07\times 10^{999}\;.$$

Since $\dfrac{\hat\varphi^{4782}}{\sqrt5}$ is clearly much less than $7\times 10^{997}$, $F_{4782}\ge 10^{999}$, and our approximation in $(2)$ did no harm.

As an extra check, note that $$\frac{\varphi^{4781}}{\sqrt5}<7\times 10^{998}\;,$$ and $\dfrac{\hat\varphi^{4781}}{\sqrt5}$ is clearly much less than $3\times 10^{998}$, so $F_{4781}<10^{999}$ and has only $999$ digits.

share|improve this answer
    
I'm still working through this, but shouldn't the middle term in the last part of (1) be negated, ie -psi^n/sqrt(5)? –  kakridge Jul 6 '12 at 15:01
    
I'm not clear on everything past "As an extra check", but the walkthrough up until that point was great. Thanks. –  kakridge Jul 6 '12 at 15:39
    
@kakridge: The extra check is just verifying that $n=4781$ really is too small, because $F_{4781}$ is too small to have $1000$ digits. –  Brian M. Scott Jul 6 '12 at 16:18

The nth fibonacci number is given exactly by a sum of two geometric progressions involving $\phi$, namely: $$F(n)=\frac{\phi^n-\frac{1}{(-\phi^n)}}{\sqrt{5}}$$ As n becomes large, the terms involving $\frac{1}{\phi^n}$ become very small, to the point where they are negligible. As a result, we can say that: $$F(n)\approx\frac{\phi^n}{\sqrt{5}}=\left[\frac{\phi^n}{\sqrt{5}}\right]$$ The rounding step is valid because the $\frac{1}{\phi^n}$ terms are so small.

share|improve this answer
    
Where did you get the 1/phi^n in the first function? –  kakridge Jul 6 '12 at 14:43
    
Apologies, that should say $\frac{1}{(-\phi)^n}$. The rest is detailed in the linked page. –  Daniel Littlewood Jul 7 '12 at 18:26
    
You should not say "geometric series". The sequence $(F(n))_{n\in\mathbf N}$ is a sum of two geometric progressions, not itself a geometric progression (since the ratio $F(n+1):F(n)$ is non-constant, even though it converges), and it is not a series at all. –  Marc van Leeuwen Jul 7 '12 at 19:05
    
Absolutely, thank you. –  Daniel Littlewood Jul 7 '12 at 19:06

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.