If people are interested in this sort of thing, there's some nice linear algebra underlying the idea.

The Fibonacci recurrence is a linear recurrence, meaning that if you have two different sequences such that

    F[n] = F[n - 1] + F[n - 2]
    G[n] = G[n - 1] + G[n - 2]

then the scalar multiples (multiply every element of F by some value k) and termwise sum of F and G will also solve this recurrence. One nice thing to do then is to search for a base p such that one solution for the recurrence is P[n] = p^n. This gives a formula for p, namely p² = p + 1, which also characterizes the golden ratio φ = (1 + √5)/2 and its negative reciprocal -1/φ = (1 − √5)/2.

Well, remember that the recurrence gives you everything if you also specify the first two numbers F[0] and F[1]. We know that these two sequences that we just computed are

    P1 = [1, (1 + √5)/2, ...]
    P2 = [1, (1 − √5)/2, ...]

and given F0, F1 you can use some simple linear algebra to solve for a and b such that:

    a P1[0] + b P2[0] = F0,
    a P1[1] + b P2[1] = F1.

This gives a closed form solution for the Nth term in terms of these Ps. So the sequences obeying the recurrence actually form a 2-dimensional vector space and these polynomials just happen to be a nice basis for that vector space.

Similarly for the case of the powers of phi, we can use this argument in reverse to say "I know I want P1 plus something times P2 which causes all of the terms to be integers," P2 will then approach zero (since it has modulus less than 1).

For this, we can look at the recurrence and say "oh, we just need the first two terms to be integers and then the recurrence makes everything else integers," so choosing a = 1, b = 1 gives us F[0] = 2, F[1] = 1, and these happen to be called the "Lucas numbers".

Similarly we could expect that the powers of any solution to p² = m p + n, integer m, n, p > 1 will be close to the integers as long as the other solution q lies somewhere in the unit interval -1 < q < 1. Completing the square gives (p − m/2)² = n + m²/4, the solutions are evenly spaced about m/2 with a distance from center to solution of √(m²/4 + n).

So for example the recurrence T[n] = 3 T[n-1] - T[n-2] is solved by the numbers (3 ± √5)/2 and so (3 + √5)/2 must also have this property, whereas T[n] = 3 T[n-1] + T[n-2] gives you (3 ± √13)/2 and has this property too.