Question on solving linear recurrence relations

In summary, the characteristic equation of a linear recurrence relation always takes the form of a polynomial equation where the coefficients are represented by constants and the variable is raised to a power. This form can be derived by assuming a form for the recurrence relation and using algebraic manipulation. The characteristic equation is equivalent to the characteristic polynomial, which is obtained by setting the polynomial equal to zero.
  • #1
93
0
Why does the characteristic equation of a linear recurrence relation always look like

an = series of constants multiplied by a number raised to n
 
Mathematics news on Phys.org
  • #2
japplepie said:
Why does the characteristic equation of a linear recurrence relation always look like

an = series of constants multiplied by a number raised to n

Unless a specific statement is made about the relation between the characteristic equation and the recurrence, we don't have any theorem to prove. The definition of the characteristic equation gives the form of the equation. Definitions are stipulations, not things to be proven or disproven. We can explain the motivation for the definition by doing some algebra.

You didn't establish much notation, so let's use the notation of the Wikipedia article http://en.wikipedia.org/wiki/Recurrence_relation.

In that article, the recurrence relation is:
[itex] a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d} [/itex] .

Assume [itex] a_n = t^n [/itex] for some unknown [itex] t [/itex]. Substitute a [itex]t^k [/itex] for each [itex] a^k [/itex] in the recurrence relation.

This gives:
[itex] t^n = c_1t^{n-1} + c_2t^{n-2}+\cdots+c_dt^{n-d} [/itex]

Assuming [itex] t\ne 0 [/itex] multiply both sides of the above equation by [itex] t^{d-n} [/itex] :

[itex] t^d = c_1 t^{d-1} + c_2t^{d-2}+\cdots+ c_d^0 [/itex]

Which is equivalent to:
[itex] 0 = t^d - c_1 t^{d-1} - c_2t^{d-2}-\cdots- c_d^0 [/itex]

---------
The above is the same as the characteristic equation:
[itex] 0 = t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d} [/itex]

Which comes from setting zero equal to the characteristic polynomial, which is:
[itex] p(t)= t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d} [/itex]

.
 

1. What is a linear recurrence relation?

A linear recurrence relation is a mathematical equation that describes the relationship between a sequence of numbers, where each term is a linear combination of previous terms. It is commonly used in the field of mathematics to model and analyze various real-world phenomena.

2. How do you solve a linear recurrence relation?

To solve a linear recurrence relation, you can use various methods such as substitution, characteristic equation, or generating functions. These methods involve finding a closed-form solution for the recurrence relation, which allows you to directly calculate any term in the sequence without having to go through all the previous terms.

3. What is the difference between a homogeneous and non-homogeneous linear recurrence relation?

A homogeneous linear recurrence relation is one where the right-hand side of the equation is equal to zero, while a non-homogeneous linear recurrence relation has a non-zero right-hand side. This difference affects the methods used to solve the recurrence relation, as non-homogeneous equations require an additional step to find the particular solution.

4. Can linear recurrence relations be used to solve real-world problems?

Yes, linear recurrence relations can be used to model and solve various real-world problems, such as population growth, economic trends, and scientific phenomena. By analyzing the recurrence relation, we can gain insights and make predictions about the behavior of a system over time.

5. Are there any limitations to using linear recurrence relations?

Yes, there are some limitations to using linear recurrence relations. They are only applicable to linear systems, which means they cannot be used to model systems with non-linear relationships. Additionally, the accuracy of the predictions made using a recurrence relation depends on the accuracy of the initial conditions and the assumptions made in the model.

Suggested for: Question on solving linear recurrence relations

Replies
12
Views
2K
Replies
8
Views
2K
Replies
3
Views
1K
Replies
2
Views
1K
Replies
0
Views
510
Replies
44
Views
3K
Replies
2
Views
1K
Replies
45
Views
2K
Replies
10
Views
2K
Back
Top