3 ms·
Yep, this is called Binet formula, and actually all linear recurrence sequences have one.
by magnio 6y ago
Yep, this is called Binet formula, and actually all linear recurrence sequences have one.
- throwaway_pdp09 6y agoWhat defines 'linear' here?
- nimish 6y agoThe solutions form a vector space
- throwaway_pdp09 6y agoI regret that does not elucidate. Does linear mean additions only? Or non-exponentiation, or something else?
- wnoise 6y agoLinear means that f(n) is a linear function of f(n-1)...f(n-k). This means that you can calculate f(n)...f(n-k+1) in terms of a matrix multiply on f(n-1)...f(n-k) (most of the matrix is empty, with ones just off the diagonal). Taking powers of the matrix lets you take more steps. Diagonalizing the matrix lets you take powers in constant time. (You may have to worry about precision. Often rounding to nearest integer after that fixes things though). If you are worried about that, or just don't have floating point, the "fastexp" algorithm turns it into logarithmic time.
- nimish 6y agoIf A and B are a solution, then A+B is also a solution. For a constant r, if C is a solution, r*C is also solution. That's it. The nice closed form of exponentials as solutions is just for linear difference equations with constant coefficients. In that case, you can always find a solution by trying λ^n and seeing what that forces λ to be -- it'll be a root of some polynomial.