| For All Solvers
OMC074 (for experts)

OMC074(F)

ユーザー解説 by tria

　この問題をエスパーで解く方法を紹介します（したがって，この解説内には厳密でない記述がたくさん登場します）．
　1xn=yn\displaystyle\frac{1}{x_n}=y_n とおくと， yn+1=yn+1yny_{n+1}=y_n+\dfrac{1}{y_n} です．差分 yn+1−yny_{n+1}-y_n を微分とみなすことにすると y′(n)=1y(n)y^\prime(n)=\dfrac{1}{y(n)} となり，この微分方程式を解くことで yny_n がおおよそ 2n\sqrt{2n} であることがわかります．ここから x1+x2+⋯+xnx_1+x_2+\cdots+x_n を評価するにあたって，思いきって 12+14+⋯+12n\displaystyle\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{4}}+\cdots+\frac{1}{\sqrt{2n}} に置き換えます．総和なので積分だと思うことにすると，これはおおよそ ∫0n12xdx=2n\displaystyle\int_0^n\frac{1}{\sqrt{2x}}dx=\sqrt{2n} となります．
　よって，極限値が 5358−1\sqrt{5358}-1 と求まります．

【2022/03/16 01:49 追記】厳密にしたものも書いておきます．まず，2n≤yn≤2n+12n\sqrt{2n}\leq y_n\leq\sqrt{2n}+\dfrac{1}{\sqrt{2n}} が帰納法より確かめられます．

証明 　n=1,2n=1,2 のときは成り立つ．x+1xx+\dfrac{1}{x} の単調性に注意すると，左側の不等号は 2n+2−2n=22n+2+2n≤12n\displaystyle\sqrt{2n+2}-\sqrt{2n}=\frac{2}{\sqrt{2n+2}+\sqrt{2n}}\leq\frac{1}{\sqrt{2n}} により 2n+2≤2n+12n\sqrt{2n+2}\leq\sqrt{2n}+\dfrac{1}{\sqrt{2n}} であるから成り立つ．また， 2n+12n+12n+12n=4n2+6n+1(2n+1)2n\sqrt{2n}+\dfrac{1}{\sqrt{2n}}+\dfrac{1}{\sqrt{2n}+\frac{1}{\sqrt{2n}}}=\dfrac{4n^2+6n+1}{(2n+1)\sqrt{2n}} である，n≥2n\geq2 に対し 4n2+6n+1(2n+1)2n≤2n+2+12n+2\dfrac{4n^2+6n+1}{(2n+1)\sqrt{2n}}\leq\sqrt{2n+2}+\dfrac{1}{\sqrt{2n+2}} が頑張って展開するとわかるので，右側の不等号も成り立つ．

∑k=1nxk=Sn\displaystyle\sum_{k=1}^nx_k=S_n とします．積分を ∑k=1n∫k−1kf(x)dx\displaystyle\sum_{k=1}^n\int_{k-1}^kf(x)dx と捉えることで，積分による概算値と実際の値との差が評価できます．

評価 　2n≤yn≤2n+12n\sqrt{2n}\leq y_n\leq\sqrt{2n}+\dfrac{1}{\sqrt{2n}} より， 12n−1(2n)3/2≤xn≤12n\displaystyle\frac{1}{\sqrt{2n}}-\frac{1}{(2n)^{3/2}}\leq x_n\leq\frac{1}{\sqrt{2n}}．Sn′=∑k=1n12k\displaystyle S^\prime_n=\sum_{k=1}^n\frac{1}{\sqrt{2k}} とすると， Sn′−2n=∑k=1n12k−∑k=1n∫k−1k12xdx=∑k=1n(12k−(2k+2−2k))=∑k=1n22k(2k+2k+2)2\displaystyle S^\prime_n-\sqrt{2n}=\sum_{k=1}^n\frac{1}{\sqrt{2k}}-\sum_{k=1}^n\int_{k-1}^k\frac{1}{\sqrt{2x}}dx=\sum_{k=1}^n\left(\frac{1}{\sqrt{2k}}-(\sqrt{2k+2}-\sqrt{2k})\right)=\sum_{k=1}^n\frac{2}{\sqrt{2k}(\sqrt{2k}+\sqrt{2k+2})^2} となり，これは O(1n)\displaystyle O\left(\frac{1}{\sqrt{n}}\right) である．∑k=1n1(2n)3/2\displaystyle\sum_{k=1}^n\frac{1}{(2n)^{3/2}} も O(1n)\displaystyle O\left(\frac{1}{\sqrt{n}}\right) であるので Sn=2n+O(1n)S_n=\sqrt{2n}+\displaystyle O\left(\frac{1}{\sqrt{n}}\right) である．