Use the principle of mathematical induction to prove [(1/2)+(1/2)+(1/3)+. . . (1/n)] ≤ (n/2)+1 for all n ϵ z+

Question

Use the principle of mathematical induction to prove $$\left[\frac{1}{1}+ \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n}\right] \leq \frac{n}{2} + 1~\text{for all}~n \in \mathbb{Z}^+$$

I have been trying to solve this however find myself getting stuck when I substitute $p_k$ back into the equation. This is my approach so far:

(1) If $n= 1$, LHS $= (1/1) = 1$ and RHS $= \frac{1}{2}+1 = \frac{3}{2}$ LHS $\leq$ RHS $p_1$ is true

Assuming $p_k$ is true, $n = k$

$$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{k} \leq \frac{k}{2}+1$$

If $p_{k+1}$ is true, $n = k+1$

$$\frac{1}{1} + \frac{1}{2}+ \frac{1}{3} + \ldots + \frac{1}{k} + \frac{1}{k+1} \leq \frac{k+1}{2} +1$$ Now LHS $\leq \frac{k}{2}+1+ \frac{1}{k+1}$ [using $p_k$]

I don't really know what to do after this in terms of proving the sequence is less than or equal to $\frac{n}{2} + 1$?

Answer 1

You have to prove that if it is true for k, it is true fro k+1.

for k>1 let's assume that p[k] is true, then (1/1)+(1/2)(1/3)...(1/k) ≤ (k/2)+1

we want to prove that p[k+1] is true in other words :

(1/1)+(1/2)+(1/3)...+(1/k)+(1/(k+1))≤(k+1)/2 +1 we have (k+1)/2 + 1 = k/2 + 1/2 + 1 = k/2 + 1 + 1/2

with p[k] we can write : (1/1)+(1/2)(1/3)... + (1/k) + 1/(k+1) ≤ k/2 + 1 + 1/(k+1) we also know that k>1 so 1/(k+1) < 1/2 so we have : (1/1)+(1/2)(1/3)... + (1/k) + 1/(k+1) ≤ k/2 + 1 + 1/2 so we have proved p[k+1]

Answer 2

Since $\frac{1}{n+1}\leq \frac{1}{2}$,

$ \begin{align*} \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{k} + \frac{1}{k+1} &\leq \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{k} + \frac{1}{2} \\ &=(\frac{k}{2}+1 )+\frac{1}{2}\\ &=\frac{k+1}{2}+1 \end{align*}$

The second to last line comes from the hypothesis which we assumed is valid for $n=k$.