Trollfaz said:
The general formula for the nth term of the Fibonacci sequence where an=an-1+an-2 can determined by matrix diagonalizations
Is there a way to determine the formula of any recursive sequence say
an=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.
