Proving asymptotics to sequences

[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.

 

[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)

 

[tacman]

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.