6 ms·
Specifically, they're nearly Lucas numbers. For those unfamiliar, the Lucas numbers are defined by the recursion L_0 = 2, L_1 = 1, and L_n = L_{n-1} + L_n. (I
by Sniffnoy 10y ago
Specifically, they're nearly Lucas numbers. For those unfamiliar, the Lucas numbers are defined by the recursion L_0 = 2, L_1 = 1, and L_n = L_{n-1} + L_n. (I.e., the Fibonacci recursion, but with different starting values.) They can also be given explicitly by L_n = phi^n + (-1/phi)^n. Since (-1/phi)^n goes rapidly to zero, phi^n will be very close to L_n. More specifically, for n>=2, (1/phi)^n < 1/2, so L_n will be the nearest integer to phi^n.
The Fibonacci numbers, meanwhile, can be given by the formula F_n = (phi^n - (-1/phi)^n) / sqrt(5). So a similar thing holds for them.
More generally, phi is a Pisot number: https://en.wikipedia.org/wiki/Pisot%E2%80%93Vijayaraghavan_number https://en.wikipedia.org/wiki/Pisot%E2%80%93Vijayaraghavan_n... Any Pisot number will have its powers approach integers at an exponential rate. (In that, the distance to the nearest integer decreases exponentially.)
- jacobolus 10y agoAnother way to get at this: φ^1 = φ φ^2 = φ + 1 [this is the definition of φ] φ^3 = φ(φ + 1) = 2φ + 1 φ^4 = φ(2φ + 1) = 3φ + 2 φ^5 = φ(3φ + 2) = 5φ + 3 φ^6 = φ(5φ + 3) = 8φ + 5 ... φ^n = F(n)φ + F(n-1) Note that F(n+1)/F(n) → φ as n → ∞. Or flipped around, F(n)φ → F(n+1). So φ^n = F(n)φ + F(n-1) → F(n+1) + F(n-1) = L(n) as n → ∞. This gets close to being an integer because F(n+1) and F(n-1) are both integers.
- deleted 10y ago[deleted]
- adrianratnapala 10y agoI'm almost with you, but you need a bit more. To show what we want, we must prove the stronger condition that F(n)φ - F(n+1) → 0. Merely knowing that F(n+1)/F(n) → φ only shows that the difference grows more slowly than F(n).
- winstonsmith 10y ago>To show what we want, we must prove the stronger condition that F(n)φ - F(n+1) → 0. Noting that {F(n+1)/F(n)} is the sequence of convergents of the continued fraction expansion of φ, your stronger condition follows from Theorem 5 at https://en.wikipedia.org/wiki/Continued_fraction https://en.wikipedia.org/wiki/Continued_fraction .
- deleted 10y ago[deleted]
- tgb 10y agoI've always enjoyed that formula for the Fibonacci numbers, primarily because it's so unintuitive that the right hand side would actually even be an integer. It's a fun exercise to prove that (without resorting to the fact that the Fibonacci numbers are obviously integers). Hint: start with -1/phi = 1-phi and use phi=(sqrt(5)+1)/2.
- jacobolus 10y ago> start with -1/phi = 1-phi and use phi=(sqrt(5)+1)/2. This is the same fact twice. (Well, the second part is just one of the two roots of the polynomial equation x^2 = x + 1.)
- btilly 10y agoThat is a special case of an even more amazing result. Given a polynomial P(x), any expression that can be written as a symmetric polynomial in the roots of P, can be written as a polynomial in the coefficients of P. See https://en.wikipedia.org/wiki/Elementary_symmetric_polynomial#The_fundamental_theorem_of_symmetric_polynomials https://en.wikipedia.org/wiki/Elementary_symmetric_polynomia... for more. This applies to arbitrary rings. So if P(x) and Q(x) are both polynomials, then any polynomial which is symmetric in the roots of P(x) and also symmetric in the roots of Q(x) can be written as polynomials in the coefficients of Q(x) and P(x). Therefore, for example, (x-sqrt(2)-sqrt(3))(x-sqrt(2)+sqrt(3))(x+sqrt(2)-sqrt(3))(x+sqrt(2)+sqrt(3)) will work out to be a polynomial in the coefficients of x^2-2 and x^2-3. It will therefore be an integer polynomial with those 4 roots. This is actually the original way in which people proved that the algebraic integers formed a ring.
- zeeZ 10y ago> L_n = L_{n-1} + L_n L_{n-1} = 0 ;-) You probably meant L_n = L_{n-2} + L_n{n-1}
- Sniffnoy 10y agoThanks! This is what happens when you decide to switch indices, I guess. Unfortunately seems I can no longer edit the comment.
- deleted 10y ago[deleted]
- 0xCAFEFARE 10y agoDude seriously explain in simpleton...?