0
$\begingroup$

Starting from $F_n = F_{k-1} F_{n-k-1} + F_{k-1} F_{n-k} + F_{k-2} F_{n-k} $

and letting $F_k \approx \phi^k$, I am hoping to find the corresponding statement for the Golden ratio:

$\phi^n = 2 \phi^{n-2} + \phi^{n-1}$ or just $\phi^2 = 2 + \phi$. Where did I go wrong?


In fact, starting from an even simpler identity: Proof of identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ for Fibonacci numbers you can get the same faulty asymptotics

$\phi^{m+n} + \phi^{m+n-2} = \phi^{m+n-1}$ or $\fbox{$\phi^2 + 1 = \phi$}$.

See also Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I tried writing $F_k F_{n-k} \approx \phi^n + \phi^{n-2k}$ still doesn't work. $\endgroup$ – cactus314 Feb 15 '14 at 20:37
  • $\begingroup$ What is your question exactly? What faulty asymptotics are you referring to? $\endgroup$ – Erick Wong Feb 15 '14 at 21:06
  • $\begingroup$ I took an existing Fibonacci identity and asked when $n,k >> 1$, what the asymptotics look like? It turns out $F_k \approx \frac{1}{\mathbf{\sqrt{5}}}\phi^k$ so and that $\frac{\phi^2 + 1}{\sqrt{5}}=\phi$. $\endgroup$ – cactus314 Feb 15 '14 at 21:27
1
$\begingroup$

The "faulty" asymptotics is caused by omission of the multiplicative constant. Such constants are often unimportant (such as in the big-Oh notation, when saying $F_n=\Theta(\phi^n)$ is perfectly correct), but sometimes play very important role.

In fact, reasoning of this kind can sometimes be used to determine the constant! For example, consider the identity $$F_{n+m}=F_{n−1}F_m+F_nF_{m+1}$$ If we assume that $F_n\approx \alpha \phi^n$, we get $$\alpha \phi^{n+m} = \alpha^2 \phi^{n+m-1} + \alpha^2 \phi^{n+m+1}$$ which reduces to $$\alpha = \frac{\phi}{1 + \phi^2}=\frac{1}{\sqrt{5}}$$ ... exactly as expected.

| cite | improve this answer | | | | |
$\endgroup$

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.