Proving asymptotics to sequences

1. Mar 21, 2007

CRGreathouse

Suppose I have a sequence

$$a_0 = 1$$

$$a_n = \sum_{k=1}^n f(k)\cdot a_{n-k}$$

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

In general, how would I go about proving that $a_n\sim g(n)$? 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.

2. Apr 18, 2007

tpm

umm..if we had the sequence :

$$a_n +b_n = \sum_{k=1}^n f(k)\cdot a_{n-k}$$

replace the sum by an integral so:

$$a(n)+b(n) = \int_{k=1}^n dkf(k)a(n-k)$$

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

$$A(s)+B(s)=F(s)A(s)$$ (using the properties of "convolution" )

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