Hacker News Reader

Comment by Sniffnoy | Hacker News Reader

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_n... Any Pisot number will have its powers approach integers at an exponential rate. (In that, the distance to the nearest integer decreases exponentially.)

View on HN

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

I'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).

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

I'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.

That 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_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.

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

Doesn't mean you can't use both of them!

Proof by hindsight!

fact comes from to do ... thoese aren't the same operations being done

> L_n = L_{n-1} + L_n

L_{n-1} = 0 ;-)

You probably meant L_n = L_{n-2} + L_n{n-1}

Thanks! This is what happens when you decide to switch indices, I guess. Unfortunately seems I can no longer edit the comment.

Dude seriously explain in simpleton...?

Reply on news.ycombinator.com