Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
$H_n$ is just shorthand for $\sum_1^n \frac{1}{n}$. –  Micah Feb 24 '13 at 22:58
1  
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
2  
@Code-Guru The = in notation f(n) = O(g(n)), does not stand for equality. –  ypercube Feb 25 '13 at 0:05
2  
I agree that it may be confusing but it's used in many Computer Science books. –  ypercube Feb 25 '13 at 0:10

5 Answers 5

up vote 5 down vote accepted

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)$$

share|improve this answer

\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}

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer
1  
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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