一道和调和级数有关的问题

最近碰到一个调和级数有关的问题，挺有意思的，这里记录一下，题目来自Mit公开课Session 23。

问题

假设一个人在沙漠里探险，他随身最多携带$1$加仑水，行走一天需要消耗$1$加仑水（为方便讨论，假设一天行走的距离为$1$），但是可以在任意地点存储水，到达任意一个地点后需要返回，例如携带$1$加仑水最多到达距离出发点$\frac 12 $的位置，因为需要来回。假设最开始他在起始点$A$并且$A$处的水无限，现在问此人能否走到离$A$任意远的地方？

考虑$A$处有$n$加仑水，其能够行走的距离，其中$n\in \mathbb N$。

当$n=1$时，由提示可知最远距离为$\frac 12 $；当$n\ge 2$时，考虑出发点为$n$加仑水和出发点为$n-1$加仑水的关系，思路如下：

首先想办法存储$n-1$加仑的水，假设存储点距离出发点为$a$，那么来回一次可以存储的加仑数为

$$1-2a$$

假设来回$k$次，那么总共存储的加仑数为

$$k(1-2a)$$

要使得上式为$n-1$，可取

$$k=n ,a=\frac 1 {2n}$$

即缓存点距离出发点的距离为$\frac 1{2n}$。注意最后一次运水后缓存点的加仑数为$n-1$，此时将身上剩下的$\frac 1 {2n}$加仑水也存储起来，利用剩下的$n-1$加仑水前进，前进距离为按此策略并且出发点为$n-1$加仑水前进的距离，最后回到存储点用剩下的$\frac 1{2n}$返回出发点$A$即可。如果记按这个策略操作，出发点为$n$加仑水达到的最远距离为$d_n$，那么不难看出

$$d_n =\frac {1}{2n} +d_{n-1}$$

特别的，我们取

$$d_1 = \frac 12$$

所以

$$\begin{aligned} d_n &= \frac 1{2n} +d_{n-1} \\ &= \frac 1{2n} +\frac 1{2(n-1)} +d_{n-2} \\ &= \ldots \\ &=\frac 12 \left(\sum_{i=1}^n \frac 1 i\right)\\ &= \frac 12 H_n \end{aligned}$$

其中

$$H_n= \sum_{i=1}^n \frac 1 i$$

而调和级数$H_n$是发散的，所以只要$n​$充分大，按此策略就能达到任意远的距离。