4
$\begingroup$

How does the sum $$f(x)=\sum_{n=1}^\infty \frac{x^n}{n^n}$$ behave asymptotically as $x\to\infty$? It appears that $f(x)$ asymptotically dominates any polynomial and is dominated by any exponential, so we might consider $\log f(x)$ rather than $f(x)$.

I apologize for having no work to show on this problem; I have no idea how to begin tackling a problem regarding the asymptotics of a function given its power series (of which there is no hope of evaluating in closed form). Hopefully an answer will provide me with some tools for doing so.

$\endgroup$
  • 4
    $\begingroup$ why do you think it's dominated by any exponential? $\endgroup$ – zhw. Dec 25 '18 at 18:22
  • $\begingroup$ Using some heuristic reasoning I guess that $$f(x) \sim e^{x/e} \sqrt{\frac{2\pi x}{e}}.$$ $\endgroup$ – Antonio Vargas Dec 26 '18 at 4:25
  • $\begingroup$ @Frpzzd How accurate do you want your asymptotics to be? I can improve my upper and lower bounds on the asymptotics of $\log f$ by the same technique as my current answer. Is it worth it? $\endgroup$ – Clement C. Dec 26 '18 at 10:51
  • $\begingroup$ @ClementC. Yes, that would be awesome! It would be nice to know $\log f$ within $O(1/x^2)$ or $O(1/x)$, but that might be a stretch... I am interested to see what magic you can work with it, though. :D $\endgroup$ – Frpzzd Dec 26 '18 at 16:53
  • $\begingroup$ @Frpzzd A priori, I can mostly improve the constant $c>1/e$ in the upper bound $\log f(x) \leq cx + o(x)$ (and also improve a bit the $o(x)$ in the lower bound). $\endgroup$ – Clement C. Dec 26 '18 at 18:58
10
$\begingroup$

Written from an airport. This is somewhat sketchy when comparing solutions to differential equations, but hopefully not too much for you to fill the gaps.

The main idea: bounding $f$ via differential partial equation.

We have $$ f'(x) = \sum_{n=1}^\infty \frac{x^{n-1}}{n^{n-1}} = \sum_{n=0}^\infty \frac{x^{n}}{(n+1)^{n}} = 1+\sum_{n=1}^\infty \frac{\frac{x^{n}}{n^n} }{\left(1+\frac{1}{n}\right)^{n}} > 1+\frac{1}{e}\sum_{n=1}^\infty \frac{x^{n}}{n^n} = 1+\frac{1}{e}f(x) \tag{1} $$ so in particular $$ f' > 1+\frac{1}{e}f \tag{2} $$ Since $f(0) = 0$, and the solution to $g' = 1+e^{-1}g$ with $g(0)=0$ is given by $g(x) = e^{x/e+1}-e$, we have $$ f(x) \geq e^{x/e+1}-e > 2e^{x/e} , \qquad x>4\tag{3} $$ ($x>4$ for the second inequality to kick in). Now, from $(1)$ we also have $$ f' < 1+f \tag{4} $$ (we can even improve this to $f' < 1+\frac{2}{3}f$), which this time gives $$ f(x) \leq e^x - 1\tag{5} $$

Overall, for $x>4$, $$ 2e^{x/e} \leq f(x) \leq e^x - 1 \tag{6} $$ which provides a loose estimate of the asymptotic growth of $f$: namely, $\boxed{f(x) = e^{\Theta(x)}}$.


Further: Improving (slightly) on the lower bound on $\log f$ by the low-order terms, and improving on the constant in the main asymptotics of the upper bound of $\log f$.

I will show $$ h(x) \leq f(x) \leq g(x) \tag{7} $$ where $$ \begin{align} \log h(x) &= \frac{1}{e}x + 4 - \log\frac{32}{3} + o(1) \tag{8}\\ \log g(x) &= \frac{256}{625}x + O(1) \tag{9} \end{align} $$ (note that $\frac{256}{625} \approx \frac{1}{e}+0.04$). Moreover, this can be improved by the same method, pushing to more accurate estimates, but this will get uglier. (One can also push the Taylor expansion above further, based on (12) and (13). I stopped at $o(1)$).

The observation is that for the upper and lower bound, we bounded uniformly the coefficients by $$ \forall n \geq 1\, \qquad \frac{1}{n^n} \leq \frac{1}{\left(1+\frac{1}{n}\right)^{n}} \cdot \frac{1}{n^n} \leq \frac{1}{e}\cdot \frac{1}{n^n} $$ to obtain the two corresponding differential equations. We can do better by handling the first few terms more tightly. Namely, we have $$ \left(1+\frac{1}{n}\right)^n = \begin{cases} \frac{1}{2} & n=1\\ \frac{4}{9} & n=2\\ \frac{27}{64} & n=3\\ \frac{256}{625} & n=4 \end{cases} $$ (and, of course, $\left(1+\frac{1}{n}\right)^n$ is decreasing to $1/e$). Thus, we can leverage this and solve instead the following two differential equations for $h$ and $g$: \begin{align} h'(x) &= 1 + \left(\frac{1}{2} - \frac{1}{e}\right) x + \left(\frac{4}{9} - \frac{1}{e}\right) \frac{x^2}{4} + \left( \frac{27}{64} - \frac{1}{e}\right) \frac{x^3}{27} + \frac{1}{e}h(x)\tag{10}\\ g'(x) &= 1 + \left(\frac{1}{2} - \frac{256}{625}\right) x + \left(\frac{4}{9} - \frac{256}{625}\right) \frac{x^2}{4} + \left( \frac{27}{64} - \frac{256}{625}\right) \frac{x^3}{27} + \frac{256}{625}g(x)\tag{11} \end{align} subject to $h(0)=g(0)=0$. Solving those gives a nasty expression, \begin{align} h(x) &= \frac{3}{32} e^{4 + \frac{1}{e}x} + \left(\frac{1}{27} - \frac{e}{64}\right) x^3 + \left(\frac{1}{4} - \frac{3 e^2}{64}\right) x^2 + \left(1 - \frac{3e^3}{32}\right) x -\frac{3e^4}{32} \tag{12} \\ g(x) &= \frac{457763671875}{137438953472}e^{\frac{256}{625}x} - \frac{491}{442368}x^3 - \frac{123299}{4194304}x^2 - \frac{195550963}{536870912}x -\frac{457763671875}{137438953472} \tag{13} \\ \end{align} leading to the claimed (8) and (9).

Below, a plot illustrating those approximations:

enter image description here

$\endgroup$
  • $\begingroup$ Note: I believe the lower bound to be tight, i.e., $\log f(x) = x/e +o(x)$. One can get closer to the constant $1/e$ by the above approach, by treating the first few terms of the series separately to get a better differential equation lower bound (since higher terms allow a better bound on $(1+1/n)^n$). $\endgroup$ – Clement C. Dec 25 '18 at 19:24
  • $\begingroup$ Note 2: actually, f(0)=0. This won't change much and the conclusion stands, but the answer needs to be edited. I'll do it when landing. $\endgroup$ – Clement C. Dec 25 '18 at 19:35
  • $\begingroup$ "Please make sure your table is in the upright position. We'll be taking off shortly... "No!!! But Frpzzd will enjoy this explanation so much more if there is a graph!!!" "Sir... please put the laptop away. " $\endgroup$ – Mason Dec 25 '18 at 19:50
  • 1
    $\begingroup$ OR take $g(x) = \frac{f(x)}{e^{x/e}},$ where you have proved that $g' > 0$ $\endgroup$ – Will Jagy Dec 25 '18 at 19:54
  • $\begingroup$ +1. Good answer. I am going to see if we can use Abel's summation formula to corroborate this work. If I find a way of doing that I will try and write it up. $\endgroup$ – Mason Dec 25 '18 at 19:56
7
$\begingroup$

There is an analogue of Laplace's method which works for sums. $n \ln(x/n)$ attains the maximum at $n = x/e$. Writing the exponent as $n \ln(x/n) = x/e - x \xi^2$, computing the expansion of $n'(\xi)$ at $\xi = 0$ and extending the integration range to $(-\infty, \infty)$, we obtain $$\frac {n'(\xi)} x = \sqrt{\frac 2 e} + c_1 \xi - \frac 1 6 \sqrt{\frac e 2} \,\xi^2 + c_3 \xi^3 + O(\xi^4), \quad \xi \to 0,\\ \sum_{n \geq 1} \frac {x^n} {n^n} = \int_{-\infty}^\infty x \left( \sqrt{\frac 2 e} - \frac 1 6 \sqrt{\frac e 2} \,\xi^2 + O(\xi^4) \right) e^{x/e - x \xi^2} d\xi = \\ \sqrt{\frac \pi 2} \,e^{x/e} \left( 2\sqrt{\frac x e} - \frac 1 {12} \sqrt{\frac e x} + O(x^{-3/2}) \right), \quad x \to \infty,$$ which gives $\ln f(x)$ with an error of order $O(x^{-2})$.

$\endgroup$
1
$\begingroup$

Similar to Maxim:

$$ \begin{align} f(a)&=\sum_{n=1}^\infty \frac{a^n}{n^n}=\sum_{n=1}^\infty e^{n \log(a/n)}\\ &\approx \int_1^\infty e^{t \log(a/t)} dt \\ &= a \int_0^a \frac{1}{u^2} e^{a \log(u) /u} du\\ &= a \int_0^a h(u) e^{a g(u)} du\\ &\approx a \sqrt{\frac{2 \pi}{a |g''(u_0)|} } h(u_0) e^{a g(u_0)} \end{align} $$

where we've used Laplace's approximation (assuming $a \gg e$) to $h(u) =\frac{1}{u^2}$ and $g(u)=\log(u)/u$, with $u_0=e$ , $g''(u_0)=-1/e^3$ . Then the approximation gives

$$f(a)\approx \sqrt{2 \pi a} \exp( a/e-1/2)$$

or

$$\log f(a)\approx \frac{a}{e} + \frac{1}{2}\log(a) + \frac{1}{2}(\log(2 \pi)-1) $$

I've not done the strict asyptotical analysis, but it looks as if the error is $o(1)$. Some numerical values

 a      log(f(a))    aprox      abs error 
3.0     1.896554    2.071883    0.175329
5.0     2.984687    3.063055    0.078368
7.5     4.150135    4.185486    0.035350
10.0    5.229637    5.249025    0.019389
20.0    9.268130    9.274393    0.006264
30.0    13.151944   13.155920   0.003976
50.0    20.766590   20.768922   0.002332
75.0    30.167102   30.168641   0.001539
100.0   39.508319   39.509468   0.001149
200.0   76.643415   76.643985   0.000570
300.0   113.634283  113.634662  0.000379
500.0   187.465736  187.465963  0.000227
750.0   279.638405  279.638556  0.000151
1000.0  371.752144  371.752257  0.000113
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.