I am faced with the following problem:
Consider the statement $\sum_{k=1}^{n} \frac{1}{k} < 3$. How to disprove this claim, for some $n$?
I have taken to disproving this by using a simple counter-example, $n=11$:
$\sum_{k=1}^{n=11} \frac{1}{k}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{11}\simeq3.0199$
Thus, the statement is proven false.
If instead of $3$ however, the number were slightly larger, the amount of manual summing I'd have to do would rise very quickly. My question however is whether or not there's a more efficient and elegant way to do this (possibly by induction)?
You can use the fact that for all $n$, \begin{align*} H_{2^{n + 1}} - H_{2^n} & = \frac{1}{2^n + 1} + \frac{1}{2^n + 2} + \cdots + \frac{1}{2^n + 2^n}\\ & \geqslant \frac{1}{2^{n + 1}} + \frac{1}{2^{n + 1}} + \cdots + \frac{1}{2^{n + 1}}\\ & = 2^n\frac{1}{2^{n + 1}}\\ & = \frac{1}{2}. \end{align*} Therefore, \begin{align*} H_{2^n} & = (H_{2^n} - H_{2^{n - 1}}) + (H_{2^{n - 1}} - H_{2^{n - 2}}) + \cdots (H_{2^1} - H_{2^0}) + H_1\\ & \geqslant \frac{1}{2} + \frac{1}{2} + \cdots + \frac{1}{2} + 1\\ & = \frac{n}{2} + 1. \end{align*} Finally, if you take $A$ any real number, then if you find an integer $n$ such that $\frac{n}{2} + 1 \geqslant A$, you deduce that $H_{2^n} \geqslant A$. In the case $A = 3$, $n = 2 \cdot (3 - 1) = 4$ works thus $H_{16} \geqslant 3$. You obviously don't obtain an optimal bound, and there are methods to obtain sharper bounds, using asymptotic developments like $H_n = \ln(n) + \gamma + \mathrm{O}\left(\frac{1}{n}\right)$.