3
$\begingroup$

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?

  • 0
    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.2012-01-07

1 Answers 1

2

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

  • 0
    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 answer2012-01-07