0
$\begingroup$

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?

  • 0
    Also relevant http://en.wikipedia.org/wiki/Fibonacci_numbers#Computation_by_rounding2012-07-05

2 Answers 2

5

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.

  • 0
    @kakridge: The extra check is just verifying that $n=4781$ really is too small, because $F_{4781}$ is too small to have $1000$ digits.2012-07-06
2

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.

  • 0
    Absolutely, thank you.2012-07-07