- #1

- 133

- 12

_{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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

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.

- #1

- 133

- 12

Is there a way to determine the formula of any recursive sequence say

a

Mathematics news on Phys.org

- #2

Science Advisor

Homework Helper

- 12,227

- 6,918

https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficientsTrollfaz said:_{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

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:

Share:

- Replies
- 8

- Views
- 352

- Replies
- 1

- Views
- 498

- Replies
- 4

- Views
- 1K

- Replies
- 3

- Views
- 793

- Replies
- 3

- Views
- 1K

- Replies
- 14

- Views
- 814

- Replies
- 7

- Views
- 1K

- Replies
- 1

- Views
- 680

- Replies
- 5

- Views
- 600

- Replies
- 3

- Views
- 203