0

Let $f(n) = \sum_{i=1}^n i^{-1}$.
Would the simplest $g(n)$ be $1$?

If we let $g(n) = 1$, then for all $n > 1$, $g(n) \le f(n)$.
To construct an upper bound, observe that since $n$ is finite, $f(n) = C$ for some $C \in \mathbb R$. (Here $C$ is the $n$th harmonic number). Then by the Archimedean Property for real numbers, $\exists N \in \mathbb N$ such that $N > C$. So for all $n > N$, $f(n) \le N.g(n)$. Combining the two bounds we have that $f(n) \in \Theta(g(n))$.

Please let me know if what I have done is valid.

Vizuna
  • 1,256
  • I'm not sure what you mean by "simplest" function, but asymptotically $f(n)\sim \log n$. – Math1000 Feb 04 '16 at 13:00
  • The notion of "simplest" is not exactly clear to me either, this was the exact wording of the homework question, so I'm assuming "simplest" means only containing the dominating term, without any constants. – Vizuna Feb 04 '16 at 13:02
  • If my approach is wrong, I'd appreciate any feedback on where I went wrong. – Vizuna Feb 04 '16 at 13:04
  • Why is $n$ finite? You should have $f(n) \le k_2 g(n), n>n_0$. This is not the case for $g(n)=1.$ – gammatester Feb 04 '16 at 13:04
  • I think I meant to say the $n$th harmonic number is finite, hence $f(n)$ is a real number. Or would that be an incorrect statement? – Vizuna Feb 04 '16 at 13:05
  • For any bound $M$ you can find $n_c$ with $H_n > M, n> n_c$ – gammatester Feb 04 '16 at 13:07
  • 1
    Yes it is divergent, and @Math1000 has already given the asymptotic form $H_n \sim \log n$. – gammatester Feb 04 '16 at 13:12
  • Ok, thanks. I'll look for a proof on the internet. – Vizuna Feb 04 '16 at 13:16
  • @Vizuna Consider the upper and lower Darboux sums of $x\mapsto x^{-1}$ on $[1,n]$ (with the partition ${1,2,\ldots,n}$). – Math1000 Feb 04 '16 at 13:26
  • This is interesting, didn't come across Darboux sums before. So the upper Darboux sum is $1 + \frac{1}{2} + ... + \frac{1}{n} = f(n)$ and the lower Darboux sum is $\frac{1}{2} + ... + \frac{1}{n}$ which is $f(n) - 1$. A lower bound for the upper Darboux sum is the area under the curve $\ln n$ and an upper bound for the lower Darboux sum is $\ln n$. Combining we have $\ln n \le f(n) \le \ln n + 1$. Is this enough to show that $f(n) \in \Theta(\ln n)$? The $+1$ is bugging me though... how to deal with it? – Vizuna Feb 04 '16 at 13:56
  • @Math1000 Forgot to tag you yesterday. How do I deal with the $+1$? – Vizuna Feb 05 '16 at 05:27
  • Asymptotically it is insignificant; $$\log(n+1)-\log(n) = \log\left(1+\frac1n\right)\stackrel{n\to\infty}\longrightarrow 0. $$ – Math1000 Feb 05 '16 at 14:02

0 Answers0