# Finding a general formula for a recursive sequence

• I
• Trollfaz
In summary, the general formula for the nth term of the Fibonacci sequence can be determined by finding the characteristic equation, solving it, and using it to derive solutions as a linear combination of exponentials. This method can also be used to determine the formula for any recursive sequence.

#### Trollfaz

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

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.

Last edited:
• • DrClaude and mfb