Is there a straight forward way to prove that $\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{31} > 3$

Question

Using brute force, it is straight forward to calculate that $\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{31} > 3$

Is there a more elegant way to demonstrate this?

What if I want to find the smallest $n$ such that $\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} > 4$

Is there a standard way to solve for $n$ without using brute force?

Answer 1

Your first inequation can be written $H_{31}>4$, where $H_n= 1+\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$

In this paper (Guo, B.-N. and Qi, F., “Sharp inequalities for the psi function and harmonic numbers”; theorem 5) this bound is proved:

$$ \ln\left(n+\frac12\right)+\gamma \le H_n \le \ln(n + e^{1-\gamma}-1)+\gamma \tag{1}$$

where $\gamma$ is the Euler Mascheroni constant ( $\approx 0.577215664901532$). This bound is much sharper than the usual ones like $\ln(n+1) < H_n < \ln(n+1)+1$ , which would be useless here.

We get

$$H_{31} \ge 4.02720321 \cdots$$

and

$$H_{30} \le 3.99580\cdots$$

which is enough for our purpose.

This is not very elegant, probably, but I doubt that you can find something much better (and for general $n$)

The bound is so remarkably tight (the true value is $H_{31}=4.027245195\cdots$) that we can use it for finding the cutting point for larger values (up to 12 at least), except for 6 where it cannot decide between 226 and 227.

Answer 2

[I'll have time later to expand on this answer but here's my initial thought]

This idea comes from a proof for proving the harmonic series diverges.

Namely, that $$\sum\limits_{n=1}^{2^k} \frac{1}{n} \geq 1 + \frac{k}{2}. $$

So you can at least put an upper bound on whatever number you want to exceed by rounding appropriately for the value of $k$.

Answer 3

The number $H_n=\sum_{k=1}^n \frac{1}{k}$ is the $n$th harmonic number. The harmonic series grows extremely slowly. You are looking at $\sum_{k=2}^n \frac{1}{k}=H_n-1$. So your question amounts to "what is the smallest harmonic number $>5$?" By brute force I've found it's $H_{83}$, so you have to add $\frac{1}{2}+\cdots+\frac{1}{83}$ to get something bigger than $4$.

If you're just interested in a few of these numbers, there's a list here.

The Digamma function is related to the harmonic numbers: $\psi(n)=H_{n-1}-\gamma$ where $\gamma$ is the Euler-Mascheroni constant. If you have a way to compute values of the digamma function, you could approximately find the correct value of $n$ and then check it by brute force. I'm not sure of a more elegant or exact approach.

Answer 4

Claim: $$\sum_{i=1}^{3^n}\frac{1}{i} \geq \frac{7}{6}+\frac{2}{3}n$$ whenever $n\geq2$.

Proof: By Mathematical Induction.

Take $n=3$, then instantly $1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{27}\geq \frac{7}{6}+2 > 3$.

Hope this is not a brutal way and this can be easily generalized.

Answer 5

BBP-type formulas for $\log(3)$ and $\log(7)$ in base $3$

$$\log(3)=\frac{1}{9}\sum_{k=0}^\infty \left(\frac{9}{2k+1}+\frac{1}{2k+2}\right)\frac{1}{9^{k}}$$

$$\log(7)=\frac{1}{3^5}\sum_{k=0}^\infty \left(\frac{405}{6k+1}+\frac{81}{6k+2}+\frac{72}{6k+3}+\frac{9}{6k+4}+\frac{5}{6k+5}\right)\frac{1}{3^{6k}}$$

give lower bounds

$$\log(3)>\left(9+\frac{1}{2}\right)\frac{1}{9}+\left(\frac{9}{3}+\frac{1}{4}\right)\frac{1}{81}=\frac{355}{324}$$

and $$\log(7)>\left(405+\frac{81}{2}+\frac{72}{3}+\frac{9}{4}+\frac{5}{5}\right)\frac{1}{3^5}=\frac{1891}{972}$$

From Series and integrals for inequalities and approximations to $\log(n)$ $$\log(2)=\frac{7}{10}-\int_0^1 \frac{x^4(1-x)^2}{1+x^2} dx$$

the upper bound

$$\log(2)<\frac{7}{10}$$

is obtained, and also the convergent approximation

$$\gamma>\frac{15}{26}$$

will be useful.

For your particular case $n=31$, the bound $$ H_n \ge \log(n+\frac12)+\gamma$$

given by @leonbloy becomes

$$\begin{align} H_{31} &\ge \log(2·31+1)-\log(2)+\gamma\\ &=2\log(3) + \log(7) - \log(2) + \gamma\\ &>2\frac{355}{324}+\frac{1891}{972}-\frac{7}{10}+\frac{15}{26}=\frac{253589}{63180}\\ &=4+\frac{869}{63180} \gt 4 \end{align}$$

which proves $H_{31}>4$.

To compute the smallest $n$ such that $H_n$ exceeds an integer $N$,

$$log\left(n+\frac{1}{2}\right)+\gamma>N$$ $$log\left(n+\frac{1}{2}\right)>N-\gamma$$ $$n+\frac{1}{2}>e^{N-\gamma}$$ $$n>e^{N-\gamma}-\frac{1}{2}$$

so

$$n=\lceil e^{N-\gamma}-\frac{1}{2}\rceil$$

The PARI code

for (N=0,28,print(N," ",ceil(exp(N-Euler)-1/2)))

shows that this formula produces the values published in http://oeis.org/A002387, although this does not imply that it agrees forever. The inequality and the formula derived here guarantees exceeding $N$, not doing so with the lowest $n$ possible, as in the OEIS sequence.