Determining the asymptotic behavior of a series - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T07:01:00Z http://mathoverflow.net/feeds/question/61350 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61350/determining-the-asymptotic-behavior-of-a-series Determining the asymptotic behavior of a series Erwin 2011-04-12T00:17:19Z 2011-09-17T06:49:45Z <p>I am trying to determine the behavior of the following series as $n\to\infty$. Let $0&lt;\mu&lt;1$ be fixed and for every positive integer $n\geq 1$, consider the function $f_n(t)$ of a real variable $t$ defined by the series $\sum_{k=0}^\infty\mu^k(1-\mu^kt)^n$. I want to determine how $f_n(t)$ behaves as $n\to\infty$ for <code>$0&lt;t&lt;1$</code> (some kind of asymptotic formula).</p> <p>Clearly $f_n(t)$ converges to $0$ for each <code>$0&lt;t&lt;1$</code>, but with what rate? And say, hypothetically, the rate is $O(1/n)$, then I would need to know at least what is $\lim_{n\to\infty}nf_n(t)$. I've tried several things for two weeks and I believe the rate of $O(1/n)$ is correct, but I can't find that limit. Any suggestions? </p> http://mathoverflow.net/questions/61350/determining-the-asymptotic-behavior-of-a-series/61358#61358 Answer by GH for Determining the asymptotic behavior of a series GH 2011-04-12T03:06:42Z 2011-04-13T23:46:58Z <p>This is my third response. I claim that for $0 &lt; t &lt; 1$ we have the uniform bounds $$\liminf_{n\to\infty}\ nt f_n(t) = \frac{-1}{\log\mu}+O(1),$$ $$\limsup_{n\to\infty}\ nt f_n(t) = \frac{-1}{\log\mu}+O(1),$$ where $O(1)$ denotes quantities that are absolutely bounded. First of all, $$f_n(t) = \int_{0-}^\infty \mu^x(1-\mu^xt)^n\ d[x]$$ $$= \int_{0}^\infty \mu^x(1-\mu^xt)^n\ dx - \int_{0-}^\infty \mu^x(1-\mu^xt)^n\ d\langle x\rangle,$$ where $x=[x]+\langle x\rangle$ is the decomposition into integral and fractional parts. Evaluating the first integral on the right, and applying integration parts on the second integral, we obtain $$f_n(t) = \frac{1-(1-t)^{n+1}}{(n+1)(-t\log\mu)}+ (1-t)^n+\int_0^\infty \frac{d}{dx}(\mu^x(1-\mu^xt)^n)\ \langle x\rangle\ dx.$$ Here $$\frac{d}{dx}(\mu^x(1-\mu^xt)^n) = (\log\mu)\mu^x(1-\mu^xt)^{n-1}(1-(n+1)t\mu^x)$$ changes sign only once, namely where $\mu^x=\frac{1}{(n+1)t}$, hence the last integral can be estimated readily by $0\leq \langle x\rangle &lt; 1$ as $$\int_0^\infty \frac{d}{dx}(\mu^x(1-\mu^xt)^n)\ \langle x\rangle\ dx\ll (1-t)^n+\frac{1}{nt}.$$ It follows that $$(n+1)tf_n(t)=\frac{-1}{\log\mu}+O_\mu(n(1-t)^{n})+O(1),$$ which implies the claim above, noting that $\lim_{n\to\infty}n(1-t)^{n}=0$.</p> <p>Based on the above argument I doubt that $\lim_{n\to\infty}n f_n(t)$ exists. More precisely, I don't think that $$\lim_{n\to\infty} n\int_0^\infty \frac{d}{dx}(\mu^x(1-\mu^xt)^n)\ \langle x\rangle\ dx$$ exists, because the integral is very sensitive on the fractional part of $\log_\mu\frac{1}{(n+1)t}$ where the derivative in the integrand changes its sign.</p> <p><strong>EDIT:</strong> It is easy to verify in an elementary fashion that $\lim_{n\to\infty} nf_n(t)$ does not always exist. Let $t:=\frac{1}{r^2}$ and $\mu:=\frac{1}{r^2}$, where $r>1$ is an integer. Then for any integer $\ell>0$ we have $$n=r^{2\ell} \ \Longrightarrow\ nf_n(t) > n\mu^{\ell-1}(1-\mu^{\ell-1}t)^n=r^2(1-1/n)^n \gg r^2,$$ $$n=r^{2\ell+1}\ \Longrightarrow\ nf_n(t) \ll r^3 e^{-r} + r \ll r.$$ For the last estimate use that $\mu^x(1-\mu^xt)^n$ increases for $x\leq\ell-\frac{1}{2}$, hence $$n\sum_{k=0}^{\ell-2}\mu^k(1-\mu^kt)^n &lt; n\int_0^{\ell-1}\mu^x(1-\mu^xt)^n\ dx &lt; r^2(1-r^{-2\ell})^{r^{2\ell+1}} &lt; r^2 e^{-r},$$ while clearly $$n\sum_{k=\ell-1}^{\infty}\mu^k(1-\mu^kt)^n &lt; n\mu^{\ell-1}(1-\mu^{\ell-1}t)^n+\frac{n\mu^\ell}{1-\mu} &lt; r^3 e^{-r}+2r.$$ Hence $\lim_{n\to\infty} nf_n(t)$ does not exist when $r$ is sufficiently large.</p> http://mathoverflow.net/questions/61350/determining-the-asymptotic-behavior-of-a-series/61375#61375 Answer by Peter Humphries for Determining the asymptotic behavior of a series Peter Humphries 2011-04-12T09:20:17Z 2011-04-13T01:03:47Z <p>Using partial summation, we have that $$\sum_{k = 0}^{K}{\mu^k(1 - \mu^k t)^n} = \frac{(1 - \mu^{K + 1})(1 - \mu^K t)^n}{1 - \mu} - \frac{nt \log \mu^{-1}}{1 - \mu} \int_{0}^{K}{\mu^x (1 - \mu^{\lfloor x \rfloor + 1}) (1 - \mu^x t)^{n-1} \: dx},$$ where $\lfloor x \rfloor$ is the integer part of $x$. By taking the limit as $K$ tends to infinity, $$\sum_{k = 0}^{\infty}{\mu^k(1 - \mu^k t)^n} = \frac{1}{1 - \mu} - \frac{nt \log \mu^{-1}}{1 - \mu} \int_{0}^{\infty}{\mu^x (1 - \mu^{\lfloor x \rfloor + 1}) (1 - \mu^x t)^{n-1} \: dx}.$$ Now a simple calculation shows that $$\frac{1}{1 - \mu} - \frac{nt \log \mu^{-1}}{1 - \mu} \int_{0}^{\infty}{\mu^x (1 - \mu^x t)^{n-1} \: dx} = \frac{(1 - t)^n}{1 - \mu}$$ by making the substitution $u = 1 - \mu^x t$. So the tricky part is the other bit of the integral, which is $$E = \frac{nt \mu \log \mu^{-1}}{1 - \mu} \int_{0}^{\infty}{\mu^{x + \lfloor x \rfloor} (1 - \mu^x t)^{n-1} \: dx}.$$ Note that as $x - 1 &lt; \lfloor x \rfloor \leq x$, we have the bounds $$A \leq E \leq \frac{1}{\mu} A$$ with $$A = \frac{nt \mu \log \mu^{-1}}{1 - \mu} \int_{0}^{\infty}{\mu^{2x} (1 - \mu^x t)^{n-1} \: dx}.$$ Once again, this isn't tricky to calculate: making the same substitution as earlier, we find that $$A = \frac{\mu}{t (1 - \mu)} \frac{1 - (nt + 1) (1 - t)^n}{n + 1}.$$</p> <p>So piecing everything together, we obtain $$\sum_{k = 0}^{\infty}{\mu^k(1 - \mu^k t)^n} = \frac{(1 - t)^n}{1 - \mu} + E$$ with $$E \asymp_{\mu} \frac{1 - (nt + 1) (1 - t)^n}{t(n + 1)}.$$ This doesn't yield a closed form for $\lim_{n \to \infty} n f_n(t)$, unfortunately, but it does show that $$\frac{\mu}{t(1 - \mu)} \leq \liminf_{n \to \infty} n f_n(t) \leq \limsup_{n \to \infty} n f_n(t) \leq \frac{1}{t (1 - \mu)}.$$</p> http://mathoverflow.net/questions/61350/determining-the-asymptotic-behavior-of-a-series/75639#75639 Answer by Erwin for Determining the asymptotic behavior of a series Erwin 2011-09-16T21:33:47Z 2011-09-16T21:33:47Z <p>As above, $\langle x\rangle$ denotes the fractional part of $x$.</p> <p>The behavior of $f_n(t):=\sum_{k=0}^\infty\mu^k(1-\mu^k t)^n$ as $n\to\infty$ in the interval $(0,1)$ is as follows. For a subsequence $n_k$ of the natural numbers, the sequence $n_kf_{n_k}(t)$ converges if and only if $\langle-\log_\mu(n_k-1)\rangle$ converges as $k\to\infty$. Moreover, if $\langle-\log_\mu(n_k-1)\rangle\to q\in [0,1]$ as $k\to\infty$, then $\lim_{k\to\infty}n_kf_{n_k}(t)=F_q(t)$ uniformly on compacts of $(0,1)$, where $$F_q(t)=\frac{\mu t}{1-\mu}\int_0^\infty\mu^{-\langle \log_\mu(s)+q\rangle}se^{-st}ds =\sum_{k=-\infty}^\infty\mu^{k-q}e^{t\mu^{k-q}}.$$</p> <p>Since $\langle-\log_\mu n\rangle_{n=1}^\infty$ is dense in $[0,1]$, it follows that all the limit points of the sequence $n f_n(t)$ are precisely the functions $F_q(t)$, $0\leq q&lt;1$. The same result is indeed valid for complex $t$ in the disk $|t-1/2|&lt;1/2$.</p> <p>The proof is a continuation of the ideas above of Humphries and GH.</p> <p>We start with summation by parts $$\sum_{k=0}^K\mu^k(1-\mu^kt)^n=\frac{(1-\mu^{K+1})(1-\mu^Kt)^n}{1-\mu}-\sum_{k=0}^{K-1}\frac{1-\mu^{k+1}}{1-\mu}[(1-\mu^{k+1}t)^n-(1-\mu^{k}t)^n]$$</p> <p>$$=\frac{(1-t)^n}{1-\mu}-\frac{\mu^{K+1}(1-\mu^Kt)^n}{1-\mu}+\sum_{k=0}^{K-1}\frac{\mu^{k+1}}{1-\mu}[(1-\mu^{k+1}t)^n-(1-\mu^{k}t)^n]$$</p> <p>Letting $K\to\infty$ we get</p> <p>$$f_n(t)=O((1-t)^n)-\frac{\mu}{1-\mu}\sum_{k=0}^\infty\mu^{k}\int_{\mu^{k+1}}^{\mu^k}\frac{d}{dx}(1-xt)^ndx$$</p> <p>$$=O((1-t)^n)+\frac{n\mu t}{1-\mu}\int_0^1\mu^{-\langle\log_\mu x\rangle}x(1-xt)^{n-1}dx$$</p> <p>$$=O((1-t)^n)+\frac{n\mu t}{(1-\mu)(n-1)^2}\int_0^{n-1}\mu^{-\langle\log_\mu [s/(n-1)]\rangle}s(1-\frac{ts}{n-1})^{n-1}ds$$</p> <p>Now, for $t\in(0,1)$, $s\in[0, n-1],$ we obviously have that</p> <p>$$0\leq 1-\frac{ts}{n-1}\leq e^{-ts/(n-1)}$$ and that there is a constant $M$ independent of $n$ such that $$|e^{-ts/(n-1)}-(1-\frac{ts}{n-1})|\leq \frac{M s^2}{(n-1)^2}.$$</p> <p>Hence $$|e^{-ts}-(1-\frac{ts}{n-1})^{n-1}|\leq |e^{-ts/(n-1)}-(1-\frac{ts}{n-1})|(n-1)e^{\frac{-ts(n-2)}{(n-1)}}$$ $$\leq \frac{M s^2e^{-ts/2}}{n-1},\quad n\geq 3,$$</p> <p>and consequently,</p> <p>$$\int_0^{n-1}\mu^{-\langle\log_\mu [s/(n-1)]\rangle}s(1-\frac{ts}{n-1})^{n-1}ds=\int_0^{n-1}\mu^{-\langle\log_\mu [s/(n-1)]\rangle}se^{-st}ds+O(1/n)$$</p> <p>which together with the equality above yields </p> <p>$$f_n(t)=\frac{n}{(n-1)^2}[\frac{\mu t}{1-\mu}\int_0^{\infty}\mu^{-\langle\log_\mu s-\log_\mu (n-1)\rangle}se^{-st}ds+O(1/n)]$$</p> <p>and the claim made at the beginning follows.</p> http://mathoverflow.net/questions/61350/determining-the-asymptotic-behavior-of-a-series/75663#75663 Answer by Brendan McKay for Determining the asymptotic behavior of a series Brendan McKay 2011-09-17T06:37:48Z 2011-09-17T06:49:45Z <p>Here is an elementary approach, which shows how to find the nature of $nf_n(t)$ as $n\to\infty$. But I'm not going to bound error terms or such so this remains an outline until those details are filled in.</p> <p>Write $a(k) = \mu^k(1-t\mu^k)^n$ and consider $k$ as a real variable. $a(k)$ is easily seen to have a unique maximum at $k=k_0$ where $\mu^{-k_0}=1/((t(n+1))$. Now calculate $$a(k_0) = \frac{(n/(n+1))^n}{t(n+1)} \sim \frac{e^{-1}}{t(n+1)}$$ $$a(k_0+u) = a(k_0) \mu^u\left(\frac{1-\mu^u/(n+1)}{1-1/(n+1)}\right)^n \sim a(k_0) \mu^u \exp(1-\mu^u)),$$ the limits being for $n\to\infty$ with $u$ not too wild.</p> <p>So now we have (modulo checking of error terms), $$nf_n(t) \sim \frac{1}{t} \sum_u \mu^u e^{-\mu^u},$$ where the sum is over $u\ge -k_0$ such that $k_0+u$ is an integer. The restriction $u\ge -k_0$ should be far enough in the tail that it doesn't matter, so we have $$nf_n(t) \sim \frac{1}{t} F_\mu(y),$$ where $y$ is the fractional part of $k_0$ and $$F_\mu(y) = \sum_{j=-\infty}^\infty \mu^{y+j}e^{-\mu^{y+j}}.$$ (Doesn't this last sum have a name? I'm sure I've seen it before.)</p>