# 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

## 1. What is a recursive sequence?

A recursive sequence is a sequence of numbers where each term is defined by a previous term or terms. This means that the formula for finding each term relies on the values of the previous terms.

## 2. Why is finding a general formula for a recursive sequence important?

Finding a general formula for a recursive sequence allows us to easily calculate any term in the sequence without having to rely on the previous terms. It also helps us understand the pattern and behavior of the sequence.

## 3. How do you find a general formula for a recursive sequence?

To find a general formula for a recursive sequence, you need to first identify the pattern or rule that governs the sequence. This can be done by looking at the differences between terms or by using algebraic manipulation. Once the pattern is identified, you can use it to create a formula that will generate any term in the sequence.

## 4. Are there any tips or tricks for finding a general formula for a recursive sequence?

One tip is to start by writing out the sequence and looking for any patterns or relationships between terms. It can also be helpful to try plugging in different values for the terms to see if you can identify a pattern. Additionally, using algebraic manipulation, such as factoring or expanding, can help reveal the underlying pattern.

## 5. Can a recursive sequence have more than one general formula?

Yes, a recursive sequence can have multiple general formulas depending on the pattern or rule that is identified. It is important to test each formula by plugging in different values to ensure that it generates the correct terms in the sequence.

Replies
4
Views
2K
Replies
11
Views
1K
Replies
8
Views
1K
Replies
15
Views
1K
Replies
4
Views
1K
Replies
5
Views
1K
Replies
5
Views
2K
Replies
1
Views
1K
Replies
1
Views
2K
Replies
1
Views
1K