对误差的分析从而改进分段估计

问题

求极限:${\lim }_{n\to \infty }\frac{n+n^{1/2}+...+n^{1/n}}{n}$

1.和的分段估计

在这个问题当中，我们无非就是要估计$S_n:={\sum }_{k\le n}{n}^{1/k}$目标精度为$o(n)$。因为这样的话我们可以得到一个关于$\frac{1}{n}{S}_n$的一个精度为$o(1)$的估计，从而得到极限。

通过对求和对象的简单观察，我们发现这些被求和对象的增长速度完全不同。第一项$n$，第二项$\sqrt{n}$都是很大的，而最后一项$n^{1/n}\sim 1$相对而言又特别小。因此直接进行逐项估计显然是不合适的，误差会特别大。同时，假设我们对于这些被求和对象$n^{1/k}$又没有特别好的估计（实际上我们有办法），想要改进精度只能从逐项估计的“底”下手。于是联想到1.3 为了控制底而进行分段。

• 关于”底乘以高”的原理与逐项估计之间的关系，参考逐项估计的开头。

想法1.1（初步方案）

1. 第一项$n$完全不动，因为$\frac{1}{n}{S}_n$第一项就是$1$，不动它精度就是最好的。
2. 在$[2,n]\cap \mathbb{N}$中间我们需要找一个断点$1\ll \phi (n)\ll n$，这样我们可以把求和写成两段${\sum }_{2\le k\le n}={\sum }_{2\le k<\phi (n)}+{\sum }_{\phi (n)\le k\le n}$然后两端分开用不同的方式进行估计。
3. 关于$\phi (n)$的选择：正是因为我们对求和对象$n^{1/k}$的无能为力（假设如此，实际上我们有办法），所以这里的分段放缩非常粗糙，精度控制全部由“底”的长度，以及分段点的位置决定。其中第一段的误差可以被这一段当中被求和对象的“振幅”乘以这一段的长度来控制，即$\begin{array}{rl}{\text{Error}}_1& \le (n^{1/\phi (n)}-\sqrt{n})\times (\phi (n)-2)\\ & =\left(1+O\left(\frac{\log (n)}{\phi (n)}\right)-\sqrt{n}\right)\times (\phi (n)-2)\\ & =O(\sqrt{n}\phi (n))\end{array}$第二段的误差也可以用类似的式子控制$\begin{array}{rl}{\text{Error}}_2& \le (n^{1/n}-n^{1/\phi (n)})\times (n-\phi (n)+1)\\ & =O\left(\frac{\log (n)}{\phi (n)}\right)\times (n-\phi (n)+1)\\ & =o(n)\end{array}$所以总的来说，只要控制好第一段我们就能得到想要的估计。
4. 首先我们尝试$\phi (n)=n^r,0<r<1$。带入上述估计结果当中得到${\text{Error}}_1\le O(n^{1/2+r})$因此只要$0<r<1/2$整个估计就能成功。

• 这里我们用到了$n^{1/\phi (n)}=1+O\left(\frac{\log (n)}{\phi (n)}\right)$这一来自于Taylor展开的结果(假设$1\ll \phi (n)\ll n$）。

现在我们执行上述方案，不妨令$\phi (n)=n^{1/3}$，于是$S_n=n+{\sum }_{2\le k\le n}{n}^{1/k}=n+{\sum }_{2\le k<n^{1/3}}{n}^{1/k}+{\sum }_{n^{1/3}\le k\le n}{n}^{1/k}$于是做放缩的话会发现$\begin{array}{rl}{S}_n& <n+\sqrt{n}(n^{1/3}-2)+n^{1/n^{1/3}}(n-n^{1/3}+1)\\ & =2n+o(n)\end{array}$以及$\begin{array}{rl}{S}_n& >n+n^{1/n^{1/3}}(n^{1/3}-2)+n^{1/n}(n-n^{1/3}+1)\\ & =2n+o(n)\end{array}$综上所述$S_n=2n+o(n)$于是$\frac{S_n}{n}=2+o(1)$于是${\lim }_{n\to \infty }\frac{n+n^{1/2}+...+n^{1/n}}{n}=2$

2. 基于Taylor展开的逐项估计

首先被求和对象$n^{1/k}=e^{\frac{\log (n)}{k}}$我们打算对被求和对象做Taylor展开。不过此处由于$e^{\frac{\log (n)}{k}}$的指数部分是有可能无界的（随着$n$增大），因此我们需要小心控制其余项。这里考虑带Lagrange余项的Taylor展开$e^{\frac{\log (n)}{k}}=1+\frac{\log (n)}{k}+\frac{1}{2}{\left(\frac{\log (n)}{k}\right)}^2\exp ({\xi }_{k,n})$其中$0<{\xi }_{k,n}<\frac{\log (n)}{k}$。如果我们用$R_{n,k}$去表示余项，那么$R_{n,k}\le \frac{{\log }^2(n)}{2k^2}{n}^{1/k}$这样的误差累积起来的估计为$\begin{array}{rl}\sum _{k=2}^n{R}_{n,k}& \le \frac{1}{2}{\log }^2(n)\sum _{k=2}^n\frac{n^{1/k}}{k^2}\\ & \le \frac{1}{2}{\log }^2(n)\sqrt{n}\sum _{k=2}^n\frac{1}{k^2}\\ & =O(\sqrt{n}{\log }^2(n))\end{array}$ 利用这个式子做逐项估计，并提前提出较为麻烦的第一项，我们得到$\begin{array}{rl}{S}_n& =n+\sum _{k=2}^n{n}^{1/k}\\ & =n+\sum _{k=2}^n\left(1+\frac{\log (n)}{k}+R_{n,k}\right)\\ & =2n-1+\log (n)(H_n-1)+\sum _{k=2}^n{R}_{n,k}\\ & =2n+{\log }^2(n)+O(\log (n))+O(\sqrt{n}{\log }^2(n))\\ & =2n+O(\sqrt{n}{\log }^2(n))\\ & =2n+o(n)\end{array}$因此我们同样得到了关于$S_n$的精度为$o(n)$的估计。

事实上我们还可以继续写下去：$\begin{array}{rl}{S}_n& =n+\sum _{k=2}^n{n}^{1/k}\\ & =n+\sqrt{n}+\sum _{k=3}^n\left(1+\frac{\log (n)}{k}+R_{n,k}\right)\\ & =2n-2+\sqrt{n}+\log (n)(H_n-H_2)+\sum _{k=3}^n{R}_{n,k}\\ & =2n+\sqrt{n}+O(n^{1/3}{\log }^2(n))\end{array}$

3. 和的积分估计

因为对于固定的$n$被求和对象$n^{1/k}$是单调减少的，因此我们想到可以用1. 和的简单积分估计：$\begin{array}{rl}{S}_n& =n+\sum _{k=2}^n{n}^{1/k}\\ & =n+{\int }_2^n{n}^{1/x}dx+O(\sqrt{n}+n^{1/n})\\ & =n+{\int }_2^n{n}^{1/x}dx+o(n)\end{array}$于是只要我们可以得到含参数积分$I_n:={\int }_2^n{n}^{1/x}dx$的精度为$o(n)$的估计我们就可以完成整个估计任务。

转化为积分是明智的选择，因为不像离散的和，对于连续的积分我们可以通过“换元”来把难以处理的积分估计转换为容易的积分估计。例如这个问题，我们可以通过换元$t=\frac{\log (n)}{x}$来使得原本的被积分对象$n^{1/x}=\exp (\frac{\log (n)}{x})$变得简单，换元后的积分变成了$I_n=\log (n){\int }_{\frac{\log (n)}{n}}^{\frac{\log (n)}{2}}\frac{e^t}{t^2}dt$新的被积函数$\frac{e^t}{t^2}$看起来就要正常多了。然后对于这个积分而言$t$的大小至关重要：

1. 当$n$足够大的时候，实际上$\frac{\log (n)}{n}$非常接近于$0$，这时候被积函数中对积分有影响的主要是$\frac{1}{t^2}$。
2. 而另一头$\frac{\log (n)}{2}$是无界的，此时被积函数中虽然$\frac{1}{t^2}$是衰减的，但是相较于$e^t$的增长而言又是微不足道的。

因此为了精度考量，此处的分段估计是十分必要的，被积分函数$\frac{e^t}{t^2}$在两段当中的行为如此不同以至于忽略差异性会导致误差巨大。

• 第一段$[1,\frac{\log (n)}{2}]$此时由于$t\ge 1$于是${\int }_1^{\frac{\log (n)}{2}}\frac{e^t}{t^2}dt\le {\int }_1^{\frac{\log (n)}{2}}{e}^{t}dt=e^{\frac{\log (n)}{2}}-e=O(\sqrt{n})$

• 第二段$[\frac{\log (n)}{n},1)$此时$t<1$，由于$t$有界于是我们此段可以考虑逐项估计，由于$e^t=1+t+\frac{t^2}{2}+O(t^3)$于是$\frac{e^t}{t^2}=\frac{1}{t^2}+\frac{1}{t}+\frac{1}{2}+O(t)$于是这一段的积分我们有$\begin{array}{rl}{\int }_{\frac{\log (n)}{n}}^1\frac{e^t}{t^2}dt& ={\int }_{\frac{\log (n)}{n}}^1\frac{1}{t^2}+\frac{1}{t}+\frac{1}{2}+O(t)dt\\ & =\frac{n}{\log (n)}+O\left(\log (n)\right)\end{array}$ 合并以上两段的估计，我们得到$I_n=n+O\left({\log }^2(n)\right)+O(\sqrt{n}\log (n))=n+o(n)$综上所述$S_n=2n+o(n)$ 所以$\frac{S_n}{n}=2+o(1)\to 2$。

• 当然这个例子当中还不足以观察出把和的估计转换为积分估计的优势。但是如果我们把问题变得更困难一些，例如体现积分估计相较于和的估计优势的一个问题当中，我们要估计$S_n:=n+{\sum }_{k=3}^n{n}^{\frac{1}{{\log }_{2}k}}$那么此时就足以体现出“转换为积分估计，然后通过换元来简化问题”这一思路的优势。