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