0
$\begingroup$

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.

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

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

$\endgroup$
3
  • $\begingroup$ 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$.) $\endgroup$ Mar 17 '19 at 9:30
  • $\begingroup$ 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. $\endgroup$ Mar 17 '19 at 11:07
  • 4
    $\begingroup$ 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. $\endgroup$
    – awkward
    Mar 17 '19 at 14:28
1
$\begingroup$

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

There is a Wikipedia page about asymptotic analysis.

$\endgroup$
1
$\begingroup$

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}}$.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Mar 17 '19 at 8:48
  • $\begingroup$ My question being: where is the error exactly? Or am I missing something in the definition? $\endgroup$ Mar 17 '19 at 8:49
  • $\begingroup$ «$F_m \sim \phi^m$» actually means $\displaystyle \lim_{m\to\infty} \dfrac{F_m}{\phi^m}$ is constant. $\endgroup$
    – Rócherz
    Mar 17 '19 at 8:52
  • $\begingroup$ 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. $\endgroup$ Mar 17 '19 at 8:54
  • $\begingroup$ @Rócherz if I might ask, can I get some sort of source for that definition? It's not so much that I doubt you as I ran into this particular snag when writing up my own answer so it would be nice to have a reputable source to cite for the non-Wikipedia definition. $\endgroup$ Mar 17 '19 at 8:54

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.