Expressing recursive sequences explicitly

  • Thread starter Nathanael
  • Start date
  • Tags
    Sequences
In summary: This gives ##x_n = n + \sum_{k=0}^{n-1} 2^k ##.In summary, the conversation discusses different methods for expressing a recurrence relation explicitly in terms of n. The first method involves assuming a specific form for x_n and using a system of equations to solve for the constants. The second method involves finding a general form for x_n based on the given function. The conversation also touches on the complexity of solving nonlinear recurrence relations and suggests a book as a resource for further exploration.
  • #1
Nathanael
Homework Helper
1,650
246
Take, for example, ##x_{n+1}=x_n+2+4n\text{ with }x_0=0##. How would you express this explicitly in terms of n?

The only method I've thought of is to assume it's of the form ##x_n=an^2+bn+c## and then write out the first few terms ##\{x_0=0,x_1=2,x_2=8\}## to get a system of equations for the constants a,b,c:

##c=0##
##a+b+c=2##
##4a+2b+c=8##
##\Rightarrow x_n=2n^2##

Does anyone have another method?Suppose I have ##x_{n+1}=x_n+2^n##. I can still find ##x_n## explicitly in the same way by assuming it's of the form ##a2^n+b##

So, if I had something like ##x_{n+1}=x_n+\sqrt{n}+n^{-\pi}##, should I then assume it's of the form ##an^{3/2}+bn^{1-\pi}+c## ?But now what about something with a nonlinear dependence on xn, like ##x_{n+1}=(n^2+n)x_n+1## or maybe even ##x_{n+1}=2^{x_n}+n##. Are there any general methods for solving these types of problems?
 
Last edited:
Mathematics news on Phys.org
  • #2
You have brought up an interesting topic. It is field of active research with ties to numerous other fields of pure and applied mathematics, e.g. dynamical systems, number theory, orthogonal polynomials.
Nathanael said:
But now what about something with a nonlinear dependence on ##x_n##, like ##x_{n+1}=(n^2+n)x_n+1##
This is still linear in ##x_n##. More precisely, it's a one-dimensional, linear non-homogeneous (because of the ##1## on the right) recurrence with non-constant (because of the ##n^2 + n## in front of ##x_n## ) coefficients.
Nathanael said:
Are there any general methods for solving these types of problems?
You may enjoy: S. Elaydi, An Introduction to Difference Equations, Springer, 3rd Edition, 2005. Incidentally, in general the answer is "no". For example, the famous logistic map ##x \mapsto r x(1 - x)## looks very simple, but may display so-called "chaotic" behavior, depending on the value of the parameter ##r##.
 
  • Like
Likes Nathanael and PeroK
  • #3
Try telescoping the terms : ## x_n - x_0 = \sum_{k=0}^{n-1} (x_{k+1} - x_k)##
 
  • Like
Likes Nathanael

1. What is a recursive sequence?

A recursive sequence is a sequence of numbers where each term is defined by the previous terms in the sequence. This means that the value of a term is dependent on the values of the previous terms.

2. How is a recursive sequence expressed explicitly?

A recursive sequence can be expressed explicitly by creating a formula that directly calculates the value of a term without relying on previous terms. This is typically done by finding a pattern or relationship between the terms in the sequence.

3. What is the difference between an explicit and recursive formula?

An explicit formula directly calculates the value of a term in a sequence, while a recursive formula uses the values of previous terms to calculate the value of the next term. Explicit formulas are generally easier to use and understand, while recursive formulas can be more complex.

4. Can all recursive sequences be expressed explicitly?

No, not all recursive sequences can be expressed explicitly. Some sequences may have more complex patterns or relationships between terms that cannot be easily expressed in a simple formula. However, many common recursive sequences can be expressed explicitly.

5. What are some real-world applications of recursive sequences?

Recursive sequences have many applications in fields such as mathematics, economics, and computer science. They can be used to model population growth, compound interest, and algorithms in computer programming. They are also used in various mathematical puzzles and games.

Similar threads

Replies
1
Views
9K
Replies
7
Views
1K
  • Calculus
Replies
13
Views
1K
Replies
1
Views
533
  • General Math
Replies
4
Views
1K
Replies
1
Views
910
  • Calculus and Beyond Homework Help
Replies
13
Views
902
  • General Math
4
Replies
125
Views
16K
  • General Math
Replies
1
Views
1K
Back
Top