I've used this website before, mostly for research purposes though. This is my first time asking a question here, so please bear with me. 😀
This question is from a homework assignment for my discrete mathematics course I'm currently taking. I've been working on this for awhile now, but I'm having a lot of trouble getting the right approach to the question. I've consulted some of my classmates regarding this question, but we can't make heads nor tails of it.
The question introduces the $n$th Harmonic Number, and states that it is defined by $$H_n = \sum_{i=1}^n \frac1i = 1 + \frac12 + \frac13 + \dots + \frac1n$$
This is fine, I've learned this in previous classes. The problematic portion is the next part:
I need to prove, by induction, that $$1 + \frac12\log_e n \leq H_n \leq 1 + \log_e n$$
Our professor gave us a hint, and I know it must be useful because it is a hint, but I'm confused about how I would apply it to this particular proof. The hint he gave is essentially that we should recall from calculus that for $0 \leq x \leq \frac12, -2x \leq \log_e(1-x) \leq -x$.
To be completely honest, I don't recall anything like that from my calculus courses. However, it must be useful in this problem but I'm not exactly sure how.
I understand the procedure for proofs by induction, and I have done a few already, in this very same homework assignment. This particular problem however is causing me some troubles. I've played around with what was given, but I can't seem to get anything that would aid me in an inductive proof. Any help for this would be greatly appreciated.
Thanks a lot in advance!
Best Answer
First of all, the reason why $-2x\leq \log(1-x)\leq -x$ comes from the Taylor approximation to $\log(1-x)$ at $0$.
Here's how to use this fact. The base case of the induction is when $n=1$, and the inequalities become $1\leq 1\leq 1$.
Now suppose that $1+\frac{1}{2}\log n\leq H_n\leq 1+\log n$. We want to prove that $$ 1+\frac{1}{2}\log (n+1)\leq H_{n+1}\leq 1+\log (n+1). $$
Starting from the inductive hypothesis, we add $\frac{1}{n+1}$ to both sides to obtain $$ \begin{align*} 1+\frac{1}{2}\log n&\leq H_n\leq 1+\log n\\ 1+\frac{1}{2}\log n+\frac{1}{n+1}&\leq H_{n+1}\leq 1+\log n+\frac{1}{n+1}\\ \end{align*} $$ Now choose $x=\frac{1}{n+1}$ in the inequality you wrote down. This gives us $$ -\frac{2}{n+1}\leq \log\left(\frac{n}{n+1}\right)=\log n-\log(n+1)\leq -\frac{1}{n+1}. $$ Therefore $\log n+\frac{1}{n+1}\leq \log(n+1)$ (from the upper inequality), and also $\log n + \frac{2}{n+1}\geq \log(n+1)$ (from the lower inequality).
Chaining this with our earlier inequality, we get $$ 1+\frac{1}{2}\log(n+1)\leq 1+\frac{1}{2}\log n+\frac{1}{n+1}\leq H_{n+1}\leq 1+\log n+\frac{1}{n+1}\leq 1+\log(n+1), $$ which is the desired result.