# Asymptotic behavior of a sequence given by a recurrence relation

Original problem is to determine asymptotic behavior of ${a_i}\left( t \right)$ as $t \to \infty$ given by recurrence relations

${a_1}\left( 0 \right) = 1$

${a_1}\left( t \right) = \frac{{2t + 1}}{{2t}}{a_1}\left( {t - 1} \right)$

${a_i}\left( t \right) = \frac{{2t + 1}}{{2t}}{a_i}\left( {t - 1} \right) + \frac{1}{{2t}}{a_{i - 1}}\left( {t - 1} \right)$

for $i \in \mathbb{N}$.

My attempt at solution:

Generating function for ${a_i}$ is $\displaystyle{F_i}\left( x \right) = \frac{{{{\left( {1 - x} \right)}^{ - \frac{3} {2}}}{{\ln }^{i - 1}}\frac{1} {{1 - x}}}} {{\left( {2i - 2} \right)!!}}$.

If we rewrite recurrence relations in a different way:

${a_1}\left( t \right) - {a_1}\left( {t - 1} \right) = \frac{1} {{2t}}{a_1}\left( {t - 1} \right)$

${a_i}\left( t \right) - {a_i}\left( {t - 1} \right) = \frac{1} {{2t}}{a_i}\left( {t - 1} \right) + \frac{1} {{2t}}{a_{i - 1}}\left( {t - 1} \right)$

And then pretend that difference operator is differential operator

${a_1}^\prime \left( t \right) = \frac{1} {{2t}}{a_1}\left( t \right)$

${a_i}^\prime \left( t \right) = \frac{1} {{2t}}{a_i}\left( t \right) + \frac{1} {{2t}}{a_{i - 1}}\left( t \right)$

by solving a system of differential equations, we get ${a_i}\left( t \right) = \frac{{\sqrt {1 + t} {{\ln }^{i - 1}}\left( {1 + t} \right)}} {{\left( {2i - 2} \right)!!}}$. Now we define ${G_i} = \sum\limits_{t = 0}^\infty {\frac{{\sqrt {1 + t} {{\ln }^{i - 1}}\left( {1 + t} \right)}} {{\left( {2i - 2} \right)!!}}{x^t}}$.

It turns out that (see http://www.math.upenn.edu/~pemantle/papers/twenty.pdf , page 210-211) if ${L_i} = \frac{{{G_i}\left( x \right)}} {{{F_i}\left( x \right)}} = \mathop {\lim }\limits_{x \to 1 - } \frac{{\sum\limits_{t = 1}^\infty {\sqrt t {x^t}{{\ln }^{i - 1}}t} }} {{x{{\left( {1 - x} \right)}^{ - \frac{3} {2}}}{{\ln }^{i - 1}}\frac{1} {{1 - x}}}} = \mathop {\lim }\limits_{x \to 1 - } \frac{{{{\left( {1 - x} \right)}^{\frac{3} {2}}}\sum\limits_{k = 1}^\infty {\sqrt k {x^k}{{\ln }^{i - 1}}k} }} {{{{\ln }^{i - 1}}\frac{1} {{1 - x}}}}$ exists and is nonzero, then $\displaystyle\mathop {\lim }\limits_{t \to + \infty } {a_i}\left( t \right) \cdot \frac{{\left( {2i - 2} \right)!! \cdot {L_i}}} {{\sqrt {t + 1} {{\ln }^{i - 1}}\left( {t + 1} \right)}} = 1$. For several values of ${L_i}$ this seems to be true, which strikes me as unexpected.

For $i = 1$ wolfram's mathematica returns ${L_1} = \frac{{\sqrt \pi }}{2}$, but can not evaluate other expressions. However, they are around 0.9 and rising as $i$ rises.

My question is how to analytically evaluate ${L_i}$, or alternatively, disregarding the previous arguments, how to determine asymptotic behavior of a sequence ${a_i}\left( t \right)$?

More generally, is it usual that the solutions of difference and corresponding differential equation (given by replacing difference operator with differential operator) have the same asymptotic behavior up to a multiplicative constant? If that is the case and such behavior is well understood, are there any textbooks about it?

-
You may be interested in Analytical Combinatorics by Flajolet and Sedgewick, which you can download here; about half of it is about extracting asymptotics of sequences from their generating functions. –  joriki Jan 7 '12 at 1:51
I upvoted your only answer (didn't understand all of it but it looked good and the OP was happy about it :-); now you have enough reputation to comment directly under David's answer. a) That would be easier to follow and b) I don't know whether David gets notified if you ping him like this in a thread where he hasn't commented. –  joriki Jan 7 '12 at 13:38

Given a generating function $q(x)$, you can often find the asymptotic behavior of its coefficients by using the Cauchy integral formula to equate the $n$th coefficient to $(2\pi i)^{-1}$ times the integral of $q(x)/x^{n+1}$ around a suitable contour, and then estimating the integral. If $q(x)$ has one singularity which is closer to the origin than all other singularities, the asymptotics of the coefficients of $q(x)$ will be determined by the behavior of $q(x)$ near this singularity, and the contour of integration should be chosen to approach this singularity. This method ("singularity analysis") is explained in detail in the Flajolet and Sedgewick book mentioned above. In particular, given the generating function $F_i(x)$ above, their Theorem VI.2 says that, for each fixed $i$, $$a_i(t)=[x^t]F_i(x)\sim\frac{2\sqrt{t} (\log t)^{i-1}}{\sqrt{\pi}(2i-2)!!}.$$ So, $L_i$ is $\sqrt{\pi}/2$, regardless of $i$.
Theorem VI.2 is for a generating function which has an additional term $\frac{1}{{{z^\beta }}}$. Could you please explain in more detail how did you get your result? Also, thank you both for the book recommendation, and yoriki for upvote –  Alen Jan 7 '12 at 13:47
Sorry, after carefully reading that page in the book, I realized that term $\frac{1}{{{z^\beta }}}$ doesn't change asymptotics of GF near 1. Thank you for your answer –  Alen Jan 7 '12 at 14:20