Proving asymptotics to sequences

  • #1
CRGreathouse
Science Advisor
Homework Helper
2,820
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.
 

Answers and Replies

  • #2
tpm
72
0
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)
 

Related Threads on Proving asymptotics to sequences

Replies
5
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
5
Views
4K
Replies
1
Views
3K
Replies
4
Views
4K
  • Last Post
Replies
1
Views
4K
Replies
10
Views
4K
  • Last Post
Replies
5
Views
5K
Replies
2
Views
4K
Top