Proving by induction that $1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}\le\frac{n}{2}+1$ holds for all $n \ge 1$

Question

While looking at some examples of proof by induction related to inequalities, I had this one that I didn't quite get:

Prove by induction that the following holds for all $n \ge 1$:

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}\le\frac{n}{2}+1$$

---

We have to prove that it holds for $n + 1$, that is:

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}+\frac{1}{n + 1}\le\frac{n > + 1}{2}+1$$

---

Hypothesis:

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}\le\frac{n}{2}+1$$

---

To prove this, we have to prove two things:

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}+\frac{1}{n+1}\le\frac{n}{2}+1+\frac{1}{n+1}$$

$$\textrm{and}$$

$$\frac{n}{2}+1+\frac{1}{n+1}\le \frac{n + 1}{2}+1$$

---

$$\textrm{* Proof goes here *}$$

My problem is with the "we have to prove these two things" part. I can see how proving them would effectively prove the whole thing, since we're trying to prove that $A \le C$, it would be the same as proving that $A \le B \land B \le C$, which seems to be what they are doing. However, under what reasoning did they decide that $B$ should be $\frac{n}{2}+1+\frac{1}{n+1}$? Was that the value necessary for $B$, or could it have been something else?

Answer 1

It is probably better to read that as "to prove this using the method below, we have to prove two things...."

Using a proof method that starts by proving that particular $A \leq B$ is a fairly natural choice in this particular instance, since it follows trivially from the inductive hypothesis, and the right hand side appears simpler than the left hand side.

Answer 2

First, check the base case $n = 1$ (trivial). Then for the inductive step, assume that the statement holds for $n = k$, that is, assume $H_k \leq k/2 + 1$, where $H_k$ is the $k$th harmonic number. Then use the inductive hypothesis to prove that $H_n \leq n/2 + 1$ also holds for $n = k + 1$. In other words, $$H_k + \frac{1}{k + 1} \leq \frac{k + 1}{2} + 1$$ is the inequality you need to prove. But this is equivalent to the first "thing" by the inductive hypothesis: just add $1/(k + 1)$ to both sides of $$H_k \leq \frac{k}{2} + 1.$$ Now you simply need to prove the second "thing" i.e. $B \leq C$ with $B = k/2 + 1 + 1/(k + 1)$ and $C = (k + 1)/2 + 1$ and you are done.