algorithm - 如何证明有重现？

Question

我有以下调和序列:

h(n) = 1 + 1/2 + 1/3 + 1/4 +...+ 1/n

我想证明有一个复发

h(n) (less than or equal to) h( lowerbound( n/2)) + 1

Answer 1

这属于 math.SE，但我们有

h(2n) - h(n) = 1/(n/2 + 1) + 1/(n/2 + 2) + ... + 1/n
             < 1/(n/2) + 1/(n/2) + ... + 1/(n/2)
             = 1,

因为有 n/2 项。我将把奇怪的情况留作练习。