Products > Dodgy Technology
Math Quirks:...Anybody (else) experienced strange Date coincidences ?
helius:
It's even possible using just integers :)
In fact that's true for any function defined as a recurrence formula, because it has a generating polynomial encompassing all of the terms of the sequence. The Fibonacci sequence just happens to be the most primitive recurrence.
SiliconWizard:
Proof there: http://mathonline.wikidot.com/a-closed-form-of-the-fibonacci-sequence
--- Quote from: helius on July 15, 2023, 07:53:52 am ---It's even possible using just integers :)
--- End quote ---
By that, I suppose you mean a closed form not involving any radicals, or any irrational numbers? Just integers, do you even mean no (non-integer) rational number either?
Would you care to share such a closed form?
helius:
$$ \DeclareMathOperator{\fibonacci}{fibonacci} \fibonacci(n) = \cases{ n & \text{if } n\lt 2\cr \left\lfloor \frac {2^{n(n+1)}}{(2^{2n} - 2^n - 1)} \right\rfloor \bmod 2^n & \text{otherwise}} $$
By the way, there's nothing special about base 2. It will work in any base, because as I said it's derived from the generating polynomial for the recurrence which is \$ \frac {1}{1 - x - x^2} \$. In some sense this polynomial is equal to the entire Fibonacci sequence.
SiliconWizard:
Sorry about the delay - yes the closed form above appears to be correct. It's rarely shown! The form with the golden ratio is much more common.
Interestingly (or is it?), from the generating function \$\displaystyle s(z) = \sum_{k = 0}^{\infty} F_k z^k = \frac{z}{1-z-z^2}\$ , with \$z = \frac{1}{2}\$, we get : \$\displaystyle \sum_{k = 0}^{\infty} \frac{F_k}{2^{k+1}} = 1\$ , while \$\displaystyle \sum_{k = 0}^{\infty} \frac{1}{2^{k+1}}\$ also converges to 1.
Circlotron:
--- Quote from: Nominal Animal on July 15, 2023, 06:31:48 am ---Yup:
$$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}, \quad \text{where} \quad \varphi = \frac{1 + \sqrt{5}}{2} \quad \text{and} \quad \psi = \frac{1 - \sqrt{5}}{2}$$
and \$\varphi \approx 1.61803\$ is the golden ratio, and \$\psi = 1 - \varphi = \frac{-1}{\varphi} \approx -0.61803\$ is its conjugate. Funky!
--- End quote ---
And of course 1/phi = phi - 1 and phi^2 = phi + 1.
What is there not to like about phi? :-+
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version