Finding a general formula for a recursive sequence

[Trollfaz]

The general formula for the nth term of the Fibonacci sequence where a_n=a_n-1+a_n-2 can determined by matrix diagonalizations
Is there a way to determine the formula of any recursive sequence say
a_n=a1+a2+...an-1

 

[jbriggs444]

The general formula for the nth term of the Fibonacci sequence where a_n=a_n-1+a_n-2 can determined by matrix diagonalizations
Is there a way to determine the formula of any recursive sequence say
a_n=a1+a2+...an-1

https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients

You solve these by finding the characteristic equation, solving that and using it to derive solutions as a linear combination of exponentials (or, when the solutions involve complex numbers, of sines, cosines and exponentials).

For Fibonacci: $a_n=a_{n-1} + a_{n-2}$, the characteristic equation is $x^2=x+1$. The characteristic equation can be found by assuming that the solution takes the form: $a_n=x^n$ and expressing the recurrence in terms of $x$.

This recurrence has two terms on the right, so it is second order. Its characteristic equation is a quadratic. A recurrence with n terms on the right is "nth order". The chacteristic equation will be a polynomial equation of the nth degree.

So one has the polynomial equation in standard form: $x^2 - x - 1 = 0$. This is a quadratic, so we can solve it with the quadratic formula to obtain $x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$. The two roots should be approximately 1.61803 and -0.61803. Call these $r_1$ and $r_2$. [These turn out to be the golden ratio $\phi$ and the additive inverse of its reciprocal. The matching decimal digits is not a coincidence. It is one of the properties of the golden ratio].

The solution to the original Fibonacci recurrence will be a linear combination: $a_n = k_1{r_1}^n + k_2{r_2}^n$. If you have the two starting terms for the recurrence, you can solve a set of simultaneous equations (via matrix algebra if you like) for $k_1$ and $k_2$.

The starting terms were referred to as "boundary conditions" when I learned this stuff. It is very much akin to solving nth order linear homogenous differential equations.