4 ms·
This is equivalent to the matrix solution. The matrix has eigenvalues φ and ψ, so working with linear combinations of powers of the matrix is the same as workin
by joppy 6y ago
This is equivalent to the matrix solution. The matrix has eigenvalues φ and ψ, so working with linear combinations of powers of the matrix is the same as working over Q(φ, ψ) = Q(√5). This is not just an equivalence abstractly mathematically, but computationally the solutions are identical and run within a constant factor of each other.
- deleted 6y ago[deleted]
- nimish 6y agoI believe it's equivalent to working in a basis that diagonalizes the matrix rather than working in the standard one. Much easier to work with.
- contravariant 6y agoIndeed (φ^n - ψ^n) / (φ - ψ) is what you'd get if you diagonalize the matrix. However the field you'd be working over is Q[√5], although really we're interested in the subring Z[φ] here. And since φ is (trivially) an eigenvalue of the matrix, let's call it M, this is equivalent to calculating in Z[M] by the Cayley-Hamilton theorem. Of course some of these constructions might be easier to work with, and certainly something like Z[x]/(x^2-x-1) allows for fairly straightforward calculation, but you're still doing the same multiplications essentially. And if you're working in a convenient ring you don't really need the ψ^n term, since you can just use that φ^n = F_{n-1} + F_{n} φ.