1
$\begingroup$

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. :D

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the detailed answer. I just have a few questions however. Firstly, why did you add 1/n+1 to each side in the first step of the inductive process? When I was playing around with the inequality, I simply replaced n with n+1 in the original inequality, and tried to see how I could get everything to make sense. Additionally, I am confused about the inequality chaining portion of the proof, as I'm not sure how you got the expressions on both absolute ends of the inequality. Again, thanks a lot for the answer, just a little more clarification for me would be great. :D $\endgroup$ – Asad Mehdi Sep 20 '15 at 23:05
  • $\begingroup$ Disregard the above comment. I understand the answer now. Adding 1/n+1 to each side is just a clever manipulation of what's given, and the absolute ends of the inequality at the end are derived from what was given in the hint. Thanks a lot. $\endgroup$ – Asad Mehdi Sep 20 '15 at 23:52

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.