# Relation between $m$th Fibonacci number and Golden Ratio

Can anyone tell me how to interpret the following expression $$F_m\sim\phi^m$$?

EDIT:

The following answer was where I have seen this notation.

• Do you know Binet formula ? Mar 17 '19 at 8:20
• Whoever wrote that meant $F_m=\mathcal{O}(\phi^m)$ (or if we're even more pedantic, $F_m\in\mathcal{O}(\phi^m)$).
– J.G.
Mar 17 '19 at 9:01
• @J.G. It would seem you are right. Can you check the edit? Mar 18 '19 at 14:47
• Which edit to what?
– J.G.
Mar 18 '19 at 15:20
• To my question. Added a link with the context. Mar 18 '19 at 16:47

It essentially implies that the $$m^{th}$$ Fibonacci number is close-ish to the $$m^{th}$$ power of the golden ratio $$\phi$$, and becomes even closer as $$m$$ grows without bound. A sort of asymptotic equivalence, if you will. I will look at this in two respects - a more intuitive and a more formal approach.

For a bit of a hand-wave-y, intuitive approach, if $$[x]$$ represents the function which rounds $$x$$ to the nearest integer, we know that

$$F_n = \left[ \frac{1}{\sqrt 5} \phi^n \right]$$

Notably, if anecdotally, for the Lucas numbers, a related sequence, we have

$$L_n = \left[ \phi^n \right]$$

We can (informally!) look at $$\sim$$ as meaning "close to" or "on the order of" (as in the terms that make the most "contribution" to the value of the functions differ by a constant multiple as the variable becomes larger and larger). Then using the rounding relation above, the result is clear: $$F_n \sim \phi^n$$ since $$F_n$$ is just a rounding of $$\phi^n/\sqrt 5$$.

It is fair to ask where that formula comes from. It is essentially tied to Binet's formula (a derivation), a closed-form relation for the Fibonacci numbers:

$$F_n = \frac{\phi^n - \bar{\phi}^n}{\sqrt 5}$$

where $$\bar \phi$$ denotes the conjugate of the golden ratio, flipping the sign on the square root, i.e. $$\bar \phi = (1 - \sqrt 5)/2$$.

Notably, $$\bar \phi \approx -0.618$$, meaning it has magnitude less than $$1$$, so as $$n$$ grows, $$\bar{\phi}^n$$ shrinks to zero. As noted in the comments by Minus One-Twelfth, the rounding relationship then comes in since $$| \bar \phi / \sqrt 5 | \approx 0.276 < 1/2$$, establishing the first relation.

We can also take a more formal approach.

The asymptotic equivalence symbol used - the $$\sim$$ - has a formal meaning beyond this "kind of close to" hand-waving I've been using, in that $$f(x) \sim g(x)$$ if

$$\lim_{x\to\infty} \frac{f(x)}{g(x)} = c$$

for some constant $$c$$ (note: $$c$$ must be a real number, it cannot be infinity). Of note, the Wikipedia article cited in Toby Mak's answer chooses $$c=1$$ (the manipulation to an arbitrary constant can be achieved simply by replacing $$f(x)$$ with $$c \cdot f(x)$$, effectively).

This tweaked definition was pointed out to me by Rócherz in the comments for Minus One-Twelfth's answer (taken essentially from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein), and can also be taken as a corollary to the big $$\Theta$$ notation or big $$O$$ notation. (An article on these sorts of notations can be found on Wikipedia or elsewhere if you want to delve further into that.)

Anyhow, we consider the limit we want to find:

$$\lim_{n\to\infty} \frac{F_n}{\phi^n}$$

We will verify the definition for $$c=1/\sqrt 5$$. From Binet's formula, then, we have

$$\frac{F_n}{\phi^n} = \frac{1}{\sqrt 5} \cdot \frac{\phi^n - \bar{\phi}^n}{\phi^n} = \frac{1}{\sqrt 5} \cdot \left(1 - \frac{\bar{\phi}^n}{\phi^n} \right)$$

It is a simple exercise in rationalizing the denominator to show that

$$\frac{\bar{\phi}}{\phi} = \frac{1}{2} \left( \sqrt 5 - 3 \right) \approx -0.382$$

and thus, since the magnitude is less than one,

$$\frac{\bar{\phi}^n}{\phi^n} \overset{n\to\infty}{\longrightarrow} 0$$

As a result, then

$$\lim_{n\to\infty} \frac{F_n}{\phi^n} = \frac{1}{\sqrt 5} \implies F_n \sim \phi^n$$

So, in short:

The notation $$F_n \sim \phi^n$$ in this context makes that $$F_n/\phi^n$$ is a constant as $$n$$ grows without bound, specifically as the limit is taken as $$n \to \infty$$.

• Nice answer! And the nearest integer relationship is basically because $\left| \frac{ {\overline{\phi}}^{n} }{\sqrt{5}} \right| < 1/2$. (If $m$ is an integer and $m= a+b$ and $|b| < 1/2$, then $m$ is the nearest integer to $a$.) Mar 17 '19 at 9:30
• What area of math are such relations a subject of? I wish to learn more about this, but I should go from some introductory textbooks. Mar 17 '19 at 11:07
• I've never seen $f(x) \sim g(x)$ used in any other sense than $f(x)/g(x) \to 1$ as $x \to \infty$; for example, that 's the definition in Asymptotic Methods in Analysis by De Bruijn. Mar 17 '19 at 14:28

The tilde symbol (~) means 'asymptotic to': as $$m$$ becomes very large, then the $$m$$th Fibonacci number will approach $$\phi^m$$.

It means that $$\lim\limits_{m\to\infty}\dfrac{F_m}{\phi^m}$$ is constant. In this particular example, we actually have $$\lim\limits_{m\to\infty}\dfrac{F_m}{\phi^m}= \dfrac{1}{\sqrt{5}}$$.
• Question: that's what it means, at least per the Wikipedia article, but my work shows that the limit is $1/\sqrt{5}$. From Binet's formula, we have $$\frac{F_n}{\phi^n} = \frac{1}{\sqrt 5} \cdot \frac{\phi^n - \bar{\phi}^n}{\phi^n} = \frac{1}{\sqrt 5} \cdot \left(1 - \frac{\bar{\phi}^n}{\phi^n} \right)$$ One can show that $$\frac{\bar{\phi}}{\phi} = \frac{1}{2} \left( \sqrt 5 - 3 \right) \approx -0.382$$ and thus, since the magnitude is less than one, $$\frac{\bar{\phi}^n}{\phi^n} \to 0$$ Here, $\bar \phi = (1 - \sqrt 5)/2$ is the conjugate of the golden ratio. Mar 17 '19 at 8:48
• «$F_m \sim \phi^m$» actually means $\displaystyle \lim_{m\to\infty} \dfrac{F_m}{\phi^m}$ is constant. Mar 17 '19 at 8:52
• Ah yes, I wasn't thinking about the particular example here. I usually use and have seen $f(n)\sim g(n)$ to mean $\lim\limits_{n\to \infty}\dfrac{f(n)}{g(n)} = 1$ ("$f(n)$ is asymptotically equivalent to $g(n)$ as $n\to \infty$"). The limit in this example is $\frac{1}{\sqrt{5}}$. Maybe OP could say where they saw the notation being used. Mar 17 '19 at 8:54