2
$\begingroup$

If $x \ge 5$, is $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{x} < \log_2 x$

I believe the answer is yes.

Here is my thinking:

(1) $\log_2{5} > 2.32 > 2.284 > 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5}$

(2) Assume up to $x$ that $\log_2 x > \sum\limits_{i \le x}\frac{1}{i}$

(3) $(x+1)^{x+1} > {{x+1}\choose{x+1}}x^{x+1} + {{x+1}\choose{x}}x^x = x^{x+1} + (x+1)x^x = 2x^{x+1} + x^x > 2(x^{x+1})$

(4) $(x+1)\log_2\left(\frac{x+1}{x}\right) > 1$

(5) $\log_2(x+1) - \log_2(x) > \frac{1}{x+1}$

(6) $\log_2(x+1) - \log_2(x) + \log_2(x) = \log_2(x+1) > \sum\limits_{i \le x+1}\frac{1}{i}$

$\endgroup$
  • $\begingroup$ See this Wikipedia article, then consider $\ln x= \ln 2\cdot \log_2 x$ $\endgroup$ – Arthur Nov 23 '18 at 7:59
  • $\begingroup$ Thanks, Arthur but I'm not clear if you are saying it is true or false. $\ln 2 < 0.694$ so that $\ln 2 < \log_2 x$. The article shows that $\ln x < 1 + 1/2 + \dots + 1/x$. I am not clear what that says about my question. $\endgroup$ – Larry Freeman Nov 23 '18 at 8:07
  • $\begingroup$ It also shows that $1+\ln x\geq1+1/2+\cdots$. $\endgroup$ – Arthur Nov 23 '18 at 8:10
  • $\begingroup$ ok. Now I get it. You are saying it is true because for $x > 11, \log_2 x > (\ln x)\frac{10}{7} > \ln x + 1$ Thanks. $\endgroup$ – Larry Freeman Nov 23 '18 at 8:17
  • $\begingroup$ And then you can check by hand which cases $x\leq 11$ it is true for as well. Exactly. $\endgroup$ – Arthur Nov 23 '18 at 8:23
2
$\begingroup$

We have that

$$1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{x} < \log_2 x \iff 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{x} < \frac{\ln x}{\ln 2}$$

$$\ln 2\left(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{x} \right)< \ln x$$

then recall that by harmonic series

$$\sum_{k=1}^x \frac1k \sim\ln x+\gamma+\frac1{2x}$$

then

$$\ln 2\left(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{x} \right) \sim \ln 2\ln x+\gamma\ln 2+\frac{\ln 2}{2x}\stackrel{?}<\ln x$$

$$(1-\ln 2)\ln x> \gamma\ln 2+\frac{\ln 2}{2x}$$

which is true for $x$ sufficiently large.

$\endgroup$
  • $\begingroup$ After "harmonic series" your summation has an error (the summand should be $1/k$) $\endgroup$ – YiFan Nov 23 '18 at 9:29
  • $\begingroup$ @YiFan Opssss...yes of course I fix the typo. Thanks! $\endgroup$ – gimusi Nov 23 '18 at 9:45
1
$\begingroup$

We can use induction as well. If we assume that it's true for $n$: $$1+\frac{1}{2}+...+\frac{1}{n}+\frac{1}{n+1}<\log_2(n)+\frac{1}{n+1}$$ So we need to prove that $$\log_2(n)+\frac{1}{n+1} < \log_2(n+1)$$ $$\frac{1}{n+1}< \log_2\left(1+\frac{1}{n}\right)$$ $$2^{\frac{1}{n+1}}<1+\frac{1}{n}$$ $$2<\left(1+\frac{1}{n}\right)^{n+1}$$ $$2<\left(1+\frac{1}{n}\right) \left(1+\frac{1}{n}\right)^n$$ And it's true, because $$1+\frac{1}{n}>1$$ And by Bernoulli's inequality: $$\left(1+\frac{1}{n}\right)^n \geq 1+n \frac{1}{n}=2$$ So we just need to find a good starting $n$. Let's check it for $n=6$: $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}<\log_2(6)$$ $$\frac{9}{20}<\log_2({6/4})$$ $$2^{\frac{9}{20}}<\frac{6}{4}$$ And by Bernoulli's inequality, $$2^{\frac{9}{20}}<1+\frac{9}{20}<1+\frac{10}{20}=\frac{6}{4}$$ So it's true $\forall n\geq 6 \land n \in \mathbb{N}$ (it's true for $n=5$ as well, but Bernoulli is not helping in that case).

$\endgroup$
1
$\begingroup$

Yes because $H_n-\log n$ is bounded by $1$ and $\log_2n$ is a multiple of $\log n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.