# Prove $1 + \frac{n}{2} \leq 1+ \frac{1}{2} +\frac{1}{3} +\cdots + \frac{1}{2^n}$ for all natural numbers $n$ [duplicate]

Definitions

• $H_n = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ for all $n \in \mathbb{N}$

The Question

• Prove $1 + \frac{n}{2} \leq H_{2^n}$ for all $n \in \mathbb{N}$

My Work

1. Base Case: $1+\frac{1}{2} \leq 1+\frac{1}{2} = H_1$
2. Inductive Hypothesis: $1 + \frac{k}{2} \leq H_{2^k}$ for all $k \in \mathbb{N}$
3. Induction Step: $1+\frac{k+1}{2} = 1+\frac{k}{2} + \frac{1}{2} \leq H_{2^k}+\frac{1}{2} \leq H_{2^k} + \frac{1}{2^k+1} + \frac{1}{2^k+2} + \cdots + \frac{1}{2^{k+1}} = H_{2^{k+1}}$

My Problem

• My problem is actually understanding the $H_{2^k}+\frac{1}{2} \leq H_{2^k} + \frac{1}{2^k+1} + \frac{1}{2^k+2} + \cdots + \frac{1}{2^{k+1}}$ step. I think that's how the proof should finish, but I don't know why.

My Question

• Can someone explain why the inequality under the "My Problem" header is true? Or if it even is true, am I going about this proof the wrong way?

## marked as duplicate by Did, uniquesolution, Arnaldo, Namaste discrete-mathematics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Mar 30 '17 at 14:17

you only require: $$\frac{1}{2^k+1} + \frac{1}{2^k+2} + \cdots + \frac{1}{2^{k+1}} = \frac{1}{2^k+1} + \frac{1}{2^k+2} + \cdots + \frac{1}{2^k+2^k} \\ =\sum_{j=1}^{2^k} \frac1{2^k+j} \\ \ge \sum_{j=1}^{2^k} \frac1{2^{k+1}} \\ = \frac12$$
• Can you explain the $\sum_{j=1}^{2^k} \frac1{2^{k+1}} \\ = \frac12$ step? – Dunka Mar 30 '17 at 9:48
If $n\leq 2^k$, then $$\frac{1}{2^k+n}\geq \frac1{2^k+2^k}=\frac1{2^{k+1}}$$ Doing this substitution, we now have a sum of $2^k$ identical fractions, which may then be simplified greatly.