# Prove that $1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n))$.

Prove that $1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n))$, with induction.

I get the intuition behind this question. Clearly, the given function isn’t even growing at a linear rate, but what is the ‘proper’ proofy way to say that $\displaystyle \sum_{k=1}^{n} \frac{1}{k} \leq \mathcal{O}(\log(n))$? I was unable to find any useful identities to use for such a summation.

-
You can prove by induction $H_{2^n}\le n+1$, where $H_n$ is $n$-th harmonic number. – xan Feb 24 '13 at 22:56
$H_n$ is just shorthand for $\sum_1^n \frac{1}{n}$. – Micah Feb 24 '13 at 22:58
More interesting is to prove $$\sum_{k=1}^n \frac{1}{k} = \Theta(\log n)$$ or even $$\sum_{k=1}^n \frac{1}{k} = \ln n + \Theta(1)$$ – Hurkyl Feb 24 '13 at 23:18
@Code-Guru The = in notation f(n) = O(g(n)), does not stand for equality. – ypercubeᵀᴹ Feb 25 '13 at 0:05
I agree that it may be confusing but it's used in many Computer Science books. – ypercubeᵀᴹ Feb 25 '13 at 0:10

I'm expanding the answer by xan:

Define $H_n=\displaystyle\sum_{1\le k\le n} {1\over k}$, let's prove by induction that $H_{2^n}\le n+1$. This is true for $n=0$ since $H_{2^0}=H_1=1\le 1$.

Now suppose $H_{2^n}\le n+1$. We have:

\begin{align} H_{2^{n+1}} &= \sum_{1\le k\le 2^{n+1}} {1\over k} \\ H_{2^{n+1}} &= \sum_{1\le k\le 2^n} {1\over k} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over k} \\ H_{2^{n+1}} &= H_{2^n} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over k} \\ H_{2^{n+1}} &\le H_{2^n} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over 2^n} \\ H_{2^{n+1}} &\le H_{2^n} + (2^n-1){1\over 2^n} \\ H_{2^{n+1}} &\le H_{2^n} + (1-{1\over 2^n}) \\ H_{2^{n+1}} &\le H_{2^n} + 1 \\ H_{2^{n+1}} &\le (n+1) + 1 \\ H_{2^{n+1}} &\le n+2 \\ \end{align}

Now let's make $m=2^n$, then $n=\lg m$, and:

$$H_{2^n}=H_m\le\lg m+1=\mathcal{O}(\log m)$$

-

\begin{align} \sum_{k=1}^n\dfrac{1}{n}&\leq1+ \int_1^n\dfrac{1}{x}dx\\&=1+\log(x)\Big|_1^n\\&=1+\log(n)-\log(1)\\&=1+\log(n)\\&=\mathcal{O}(\log(n)) \end{align}

-
It should be $\sum_{k=1}^n\frac1k\le1+\int_1^n\frac1x dx$. – user1551 Feb 24 '13 at 22:53
Sorry, I forgot a big detail, it's supposed to be a proof by induction. – John Lotacs Feb 24 '13 at 22:55

Using the inequality $1+x\le e^x$, we can derive $$\log\left(\frac{n+1}{n}\right)=\log\left(1+\frac1n\right)\le\frac1n\le-\log\left(1-\frac1n\right)=\log\left(\frac{n}{n-1}\right)\tag{1}$$ Summing $(1)$ yields $$\log(n+1)\le\sum_{k=1}^{n}\frac1k=1+\sum_{k=2}^{n}\frac1k\le1+\log(n)\tag{2}$$ That is, for all $n\ge1$ $$\log(n+1)\le\sum_{k=1}^{n}\frac1k\le1+\log(n)\tag{3}$$

Sums can easily be made into inductions. We will prove $(3)$ by induction using $(1)$.

For $n=1$, $(3)$ holds since $\log(2)\le1\le1$.

Suppose we have $(3)$ for $n-1$: $$\log(n)\le\sum_{k=1}^{n-1}\frac1k\le1+\log(n-1)\tag{4}$$ Inequality $(1)$ says that $$\log\left(\frac{n+1}{n}\right)\le\frac1n\le\log\left(\frac{n}{n-1}\right)\tag{5}$$ Adding $(4)$ to $(5)$ yields $$\log(n+1)\le\sum_{k=1}^{n}\frac1k\le1+\log(n)\tag{6}$$ which is $(3)$ for $n$. This finishes the induction.

-

Hint: Think about the integral $\displaystyle\int_1^n \frac{dx}x$.

-
Why should he think about it if someone will give him the solution in a minute or two anyway? – GEdgar Feb 25 '13 at 1:46

You want to show that $\sum_{k=1}^{n} \frac{1}{k} \leq \mathcal{O}(\log(n))$. This means that there is a constant $c > 0$ and an integer $n_0$ such that $\sum_{k=1}^{n} \frac{1}{k} \leq c\log(n)$ for all $n \ge n_0$.

Suppose that this is true for some $n$ and $c$. We want to show that $\sum_{k=1}^{n+1} \frac{1}{k} \leq c\log(n+1)$ follows.

By the induction hypothesis, $\sum_{k=1}^{n+1} \frac{1}{k} = \sum_{k=1}^{n} \frac{1}{k} + \frac1{n+1} \leq c \log(n) + \frac1{n+1}$ .

If we could show that $c \log(n) + \frac1{n+1} \le c \log(n+1)$, we would be done. But $\log(n+1) - \log(n) = \log(1+1/n) > 1/n > 1/(n+1)$, so this inequality holds for any $c \ge 1$.

To find a particular $c$ and $n_0$, look at $n = 3$. $1 + 1/2 + 1/3 < 2 < c \log 3$ for $c = 2$. So $c=2$ will work.

Of course the best value of $c$ is 1, but that is not needed for a $\mathcal{O}$ result - there just needs to be some $c$.

-