i=1n1ilogn\sum\limits_{i=1}^n\dfrac{1}{i}\approx\log n i=1nni<nlogn\sum\limits_{i=1}^n\dfrac{n}{i}<n\log n

证明:

$\dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}+\dfrac{1}{5}+\dfrac{1}{6}+\dfrac{1}{7}+\dfrac{1}{8}+\dots+\dfrac{1}{2^k-1}$

$<\dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{8}+\dots+\dfrac{1}{2^k-1}$

=1+1+1++1=1+1+1+\dots+1

1++12k1<k=log2k∴1+\dots+\dfrac{1}{2^k-1}<k=\log2^k

1++1n<logn∴1+\dots+\dfrac{1}{n}<\log n