17
$\begingroup$

I want to estimate the value of this sequence for large $n$ (with a reasonable lower bound and upper bound).

That is, can we find a function $f(n)$ such that $$ \frac{1^n + 2^{n-1} + 3^{n-2} + \cdots + n^1}{f(n)} \rightarrow 1?$$

I tried to approximate $ (n - x)^x $ as a Gaussian, look at how close it is visually, but the manipulation escapes me.

Here is the case where $n=20$:

Addendum: This post might be relevant.

$\endgroup$
8
  • 1
    $\begingroup$ The largest term is at $x$ where $x+x\ln x=n$. The second derivative will let you find the standard deviation. $\endgroup$
    – Empy2
    Jul 14 '20 at 6:38
  • 4
    $\begingroup$ Try Laplace's method: the sum $\sum_{j=1}^n j^{n-j+1}$ can be approximated by $$\int_1^n x^{n-x+1} dx \approx \int_1^n e^{(n-x+1) \operatorname{ln}(x)}dx.$$ en.wikipedia.org/wiki/Laplace%27s_method $\endgroup$ Jul 14 '20 at 6:40
  • 3
    $\begingroup$ If $$F(x)=e^x+2\left(\dfrac{e^{x}}{2}\right)^2+3\left(\dfrac{e^{x}}{3}\right)^3+\cdots+n\left(\dfrac{e^{x}}{n}\right)^n,$$ then $$F^{(n)}(0)=1^n + 2^{n-1} + 3^{n-2} + \cdots + (n-1)^2+n.$$ $\endgroup$
    – Bumblebee
    Jul 14 '20 at 7:37
  • 1
    $\begingroup$ With the optimized parameters, the plot is much more symmetric even if, compared to your approximation, the infinite norm is only divided by a factor of 2. $\endgroup$ Jul 15 '20 at 15:17
  • 2
    $\begingroup$ Maybe look at Asymptotics of $1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1$ ? $\endgroup$
    – Sil
    Jul 16 '20 at 17:48
12
+300
$\begingroup$

If you let $m_n>1$ be the unique solution to $m_n = \frac{n}{1+\ln(m_n)}$ and $S_n=\sum_{k=1}^n k^{n-k}$ (I have shifted n by one as in your plots), then $$ \lim_{n\rightarrow +\infty} \frac{1}{S_n} m_n^{n-m_n+1} \sqrt{\frac{2\pi}{m_n+n}} =1.$$ This is what you would suspect using the method of Laplace, writing $x^{n-x}=e^{f_n(x)}$ approximating $f_n$ by a parabola at the maximum (which is for $x=m_n$) and calculating the resulting gauss integral. I didn't check rigorously if the third order correction to the Laplace formula is negligible but numerically the above seems to hold.


EDIT: Let me outline a sketch of a proof (filling in details would probably amount to writing about 3 pages, dense with formulae). It follows more or less known lines in the case of Stirlings formula.

Step 1: Show that $\sum_{k=1}^n k^{n-k}$ is equivalent to the integral $\int_1^n e^{f_n(x)}dx$ with $f_n(x)=(n-x)\ln(x)$ as $n\rightarrow +\infty$. This is not so difficult.

Step 2: We write $m=m_n$. Substituting $x=m+ t \frac{m}{\sqrt{m+n}}$ and using $\ln m = \frac{n-m}{m}$ one obtains after some algebra: \begin{align} f_n(x) & = m \left( \frac{n-m}{m} - \frac{t}{\sqrt{n+m}}\right) \left( \frac{n-m}{m} + \ln \left(1+ \frac{t}{\sqrt{n+m}} \right)\right)\\ & = m\left(\frac{n-m}{m}\right)^2 -\frac{t^2}{2} + O\left(\frac{t^3}{\sqrt{n}}\right)\end{align} and then $ \int_1^n e^{f_n(x)} dx = \frac{m_n^{n-m_n+1}}{\sqrt{n+m}} \int_{-l_n}^{u_n} \exp \left( -\frac{t^2}{2} + O \left( \frac{t^3}{\sqrt{n}}\right)\right)\; dt.$ Here, $l_n,u_n\rightarrow +\infty$ as $n$ goes to infinity and pointwise the integrand goes to $e^{-t^2/2}$.

Step 3: Show that the integrand is bounded uniformly in $n$ by an integrable function and apply Lebesgue dominated convergence to conclude the proof.

For Step 3, note that a Gaussian function would not work as a dominating function due to the logarithmic tail in $f_n$. You need to construct the dominating function in a more clever way. This is where calculations become more ugly and I leave it aside.

$\endgroup$
4
  • $\begingroup$ (+1) It is a nice solution. It should be $m_n + n$ rather than $m+n$? Also, $m_n = \mathrm{e}^{W(n\mathrm{e}) - 1} = \frac{n}{W(n\mathrm{e})}$ where $W$ is the Lambert W function. Hope to see rigorous proofs of the limit equal to one. $\endgroup$
    – River Li
    Jul 19 '20 at 2:53
  • $\begingroup$ @RiverLi Thanks. Ii is indeed $m_n$. I have corrected. The problem is nice, but looks to me more complicated to prove than Stirling's formula (more terms to control) and Stirling's itself requires a couple of pages to prove rigorously. $\endgroup$
    – H. H. Rugh
    Jul 19 '20 at 7:00
  • $\begingroup$ @RiverLi In case you are still interested. I have added an outline of a proof. $\endgroup$
    – H. H. Rugh
    Jul 20 '20 at 6:49
  • $\begingroup$ It is nice. Thanks. $\endgroup$
    – River Li
    Jul 20 '20 at 8:07
9
$\begingroup$

Partial answer: $(a-x)^x= Ae^{-(x-b)^2/c}+O(|x-b|^3)$

Taking logs $$x\ln(a-x)=\ln A-(x-b)^2/c$$

Let $x=b+y$, then expanding out gives $$b\ln(a-b)+y\ln(a-b)-\frac{b}{a-b}y-\frac{1}{a-b}y^2-\frac{b}{2(a-b)^2}y^2+O(y^3)=\ln A-\frac{y^2}{c}$$

Comparing the terms we need $$\ln A=b\ln(a-b),$$ $$(a-b)\ln(a-b)=b,$$ $$\frac{1}{c}=\frac{1}{a-b}+\frac{b}{2(a-b)^2}=\frac{2a-b}{2(a-b)^2}.$$ These determine $b,A,c$ for the best fit.

Checking with the example $a=20$, gives $b=13.16$, $c=-3.49$, $A=9.7\times10^{10}$.

This suggests we take $A\sqrt{\pi c}=\sqrt{2\pi}\frac{(a-b)^{b+1}}{\sqrt{2a-b}}$ as the approximation of the sum.

Comparing the sum for $n=a=10,\ldots,20$ gives

$$Sum(n)=11377, 49863, 232768, 1151914, 6018785, 33087205, 190780212, 1150653920, 7241710929, 47454745803, 323154696184$$

$$Approx(n)=11374, 49845, 232672, 1151410, 6016080, 33072000, 190692000, 1150120000, 7238320000, 47432600000, 323004000000$$

$\endgroup$
2
  • $\begingroup$ H.H.Rugh's answer is the same, with $m_n=a-b$. $\endgroup$ Jul 14 '20 at 9:09
  • $\begingroup$ I used your answer to make all analytical. Cheers :-) $\endgroup$ Jul 15 '20 at 9:51
4
$\begingroup$

Starting from @Chrystomath's answer, for a given value of $a$ we have analyical expressions for $A$, $b$ and $c$.

The trick is to rewrite his/her second equation $$(a-b)\ln(a-b)=b$$ $$(a-b)+(a-b)\ln(a-b)=a \implies k+k \log(k)=a \implies k=\frac{a}{W(e a)}$$ where $W(.)$ is Lambert function. So, this gives $$\color{blue}{A=k^{a-k}\qquad b=a-k \qquad c=\frac{2 k^2}{a+k}}\qquad \text{with} \qquad \color{red}{k=\frac{a}{W(e a)}}$$ and then $$A\sqrt{\pi c}= k^{a-k+1} \sqrt{\frac{2 \pi}{a+k}}$$ Rounding the numbers, for $a=20$, this generates the sequence $$\{2,4,9,23,66,210,733,2780,11374,49845,232672,1151412,6016082,33072048,190691716, 1150116697,7238323772,47432585137,323004401255,2281724622065, 16693240814087\}$$ instead of $$\{1,3,8,22,65,209,732,2780,11377,49863,232768,1151914,6018785,33087205,190780212,11 50653920,7241710929,47454745803,323154696184, 2282779990494, 16700904488705\}$$

Edit

All the work can be done without expansions but instead function identification at a single point.

Consider $$f(x)=(a-x)^x $$ $$f'(x)=(a-x)^x \left(\log (a-x)-\frac{x}{a-x}\right)$$ $$f''(x)=(a-x)^{x-2} \left((a-x) \log (a-x) ((a-x) \log (a-x)-2 x)-2 a+x^2+x\right)$$ $$ g(x)=A e^{-\frac{(x-b)^2}{c}}$$ $$g'(x)=-\frac{2 A (x-b) e^{-\frac{(x-b)^2}{c}}}{c}$$ $$ g''(x)=-\frac{2 A e^{-\frac{(b-x)^2}{c}} \left(c-2 (b-x)^2\right)}{c^2}$$ Compute $x_*$ corresponding to $f'(x)=0$ and then solve for $(A,b,c)$ the equations $$f(x_*)=g(x_*) \qquad \qquad f'(x_*)=g'(x_*) \qquad \qquad f''(x_*)=g''(x_*) $$ For sure, this leads to the same results.

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