Lagrange has shown that the solution of a k-th order linear recurrence relation can be expressed in terms of the distinct solutions of its characteristic equation and their multiplicities. This paper shows that such a solution can also be expressed in terms of just one solution of the characteristic equation and the solution of a (k 1)-th order linear recurrence relation. Using this, an explicit solution to an arbitrary third, and the most general case of an arbitrary fourth, order linear recurrence relation are obtained.
展开▼