# Solving Fibonaccis Term Using Golden Ratio Convergance

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?

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.

• 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.

• 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. – preferred_anon 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. – preferred_anon Jul 7 '12 at 19:06