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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – kakridge Jul 6 '12 at 15:01
  • $\begingroup$ I'm not clear on everything past "As an extra check", but the walkthrough up until that point was great. Thanks. $\endgroup$ – kakridge Jul 6 '12 at 15:39
  • $\begingroup$ @kakridge: The extra check is just verifying that $n=4781$ really is too small, because $F_{4781}$ is too small to have $1000$ digits. $\endgroup$ – Brian M. Scott Jul 6 '12 at 16:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where did you get the 1/phi^n in the first function? $\endgroup$ – kakridge Jul 6 '12 at 14:43
  • $\begingroup$ Apologies, that should say $\frac{1}{(-\phi)^n}$. The rest is detailed in the linked page. $\endgroup$ – preferred_anon Jul 7 '12 at 18:26
  • $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Jul 7 '12 at 19:05
  • $\begingroup$ Absolutely, thank you. $\endgroup$ – preferred_anon Jul 7 '12 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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