Proving asymptotics to sequences

In summary, the conversation discussed a sequence with a known function and the desire to prove that it is asymptotically equivalent to another function. The speaker mentioned using first and second differences to estimate the function, but was open to suggestions for better methods. A suggestion was made to use Laplace transforms and the properties of convolution to obtain an asymptotic expression for the sequence.
  • #1
CRGreathouse
Science Advisor
Homework Helper
2,844
0
Suppose I have a sequence

[tex]a_0 = 1[/tex]

[tex]a_n = \sum_{k=1}^n f(k)\cdot a_{n-k}[/tex]

where f(n) is a known function (in binomial coefficients, powers, and the like).

In general, how would I go about proving that [itex]a_n\sim g(n)[/itex]? I'm working on more closely estimating the function by calculating its value for large n, along with first and second differences. (Suggestions on better methods are welcome, though I think I'm nearly there -- the second differences look suspiciously hyperbolic.)

Any help would be appreciated.
 
Physics news on Phys.org
  • #2
umm..if we had the sequence :

[tex]a_n +b_n = \sum_{k=1}^n f(k)\cdot a_{n-k}[/tex]

replace the sum by an integral so:

[tex]a(n)+b(n) = \int_{k=1}^n dkf(k)a(n-k) [/tex]

if you obtain A(s) F(s) and B(s) as the Laplace transform of a(n) b(n) and f(k)

[tex]A(s)+B(s)=F(s)A(s) [/tex] (using the properties of "convolution" )

invertng you could get an asymptotic expression for a(n)
 
  • #3


To prove asymptotics for a sequence, we need to show that the ratio of the nth term and the desired function g(n) approaches 1 as n approaches infinity. In other words, we need to show that a_n/g(n) approaches 1 as n approaches infinity.

One approach to proving this is by using induction. We can start by showing that the statement is true for n = 0, as a_0 = 1 and g(0) = 1. Then, assuming it is true for some arbitrary k, we can show that it also holds for k+1. This can be done by expanding the definition of a_n and using the induction hypothesis to simplify the expression. If we can show that the ratio a_n/g(n) approaches 1 as n approaches infinity for all n, then we have proven that a_n is asymptotic to g(n).

Another approach is to use the limit definition of asymptotics. We can take the limit as n approaches infinity of the ratio a_n/g(n) and show that it equals 1. This can be done by using techniques such as L'Hopital's rule or by simplifying the expression using known properties of the function f(n). If the limit is equal to 1, then we have proven that a_n is asymptotic to g(n).

In terms of estimating the function and calculating its value for large n, one approach is to use known properties of the function f(n) and see how it affects the overall expression. For example, if f(n) is a polynomial, we can use the binomial theorem to expand the expression and see if it simplifies to a known function that is asymptotic to g(n). We can also use techniques such as integration or summation to simplify the expression and see if it leads to an asymptotic function.

In conclusion, proving asymptotics for a sequence involves showing that the ratio of the nth term and the desired function approaches 1 as n approaches infinity. This can be done through techniques such as induction or using the limit definition of asymptotics. Additionally, using known properties of the function f(n) and simplifying the expression can also help in proving the desired asymptotic function.
 

1. What is the definition of asymptotic behavior in sequences?

Asymptotic behavior in sequences refers to the long-term behavior or trend of a sequence as its terms approach infinity. It describes how the terms of a sequence gradually approach a certain value or grow without bound.

2. How do you prove the asymptotic behavior of a sequence?

To prove the asymptotic behavior of a sequence, you can use various methods such as the limit comparison test, ratio test, or root test. These methods involve comparing the given sequence to a known sequence with a known asymptotic behavior and showing that they have a similar behavior.

3. What is the significance of proving the asymptotic behavior of a sequence?

Proving the asymptotic behavior of a sequence is important in understanding the long-term trend of the sequence, which can provide valuable insights in various fields such as economics, physics, and computer science. It also helps in determining the convergence or divergence of a sequence.

4. Can a sequence have more than one asymptotic behavior?

Yes, a sequence can have more than one asymptotic behavior. This can occur when the sequence has different behaviors for different parts of its domain or when there are multiple terms in the sequence that have a significant impact on its behavior.

5. Are there any real-life applications of proving asymptotic behavior of sequences?

Yes, proving asymptotic behavior of sequences has many real-life applications, such as in predicting the growth or decay of populations in biology, analyzing the performance of algorithms in computer science, and studying the behavior of financial markets in economics.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
975
  • Linear and Abstract Algebra
Replies
10
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
Replies
27
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
757
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Calculus and Beyond Homework Help
Replies
4
Views
876
  • Calculus and Beyond Homework Help
Replies
1
Views
230
  • General Math
Replies
1
Views
847
Back
Top