How to use mathematical induction with inequalities? I've been using mathematical induction to prove propositions like this:
$$1 + 3 + 5 + \cdots + (2n-1) = n^2$$
Which is an equality. I am, however, unable to solve inequalities. For instance, this one:
$$ 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \leq \frac{n}{2} + 1 $$
Every time my books solves one, it seems to use a different approach, making it hard to analyze. I wonder if there is a more standard procedure for working with mathematical induction (inequalities).
There are a lot of questions related to solving this kind of problem. Like these:


*

*How to prove $a^n < n!$ for all $n$ sufficiently large, and $n! \leq n^n$ for all $n$, by induction? - in this one, the asker was just given hints (it was homework)

*How to prove $n < n!$ if $n > 2$ by induction? Ilya gave an answer, but there was little explanation (and I'd like some more details on the procedure)

*how: mathematical induction prove inequation Also little explanation. Solving it with one line is great, but I'd prefer large blocks of text instead.


Can you give me a more in depth explanation of the whole procedure?
 A: The inequality certainly holds at $n=1$. We show that if it holds when $n=k$, then it holds when $n=k+1$. So we assume that for a certain number $k$, we have 
$$1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{k} \le \frac{k}{2}+1.\tag{$1$}$$
We want to prove that the inequality holds when $n=k+1$. So we want to show that
$$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{k}+\frac{1}{k+1}\le\frac{k+1}{2}+1.\tag{$2$}$$
How shall we use the induction assumption $(1)$ to show that $(2)$ holds? Note that the left-hand side of $(2)$ is pretty close to the left-hand side of $(1)$. The sum of the first $k$ terms in $(2)$ is just the left-hand side of $1$. So the part before the $\frac{1}{k+1}$ is, by $(1)$, $\le \frac{k}{2}+1$. 
Using more formal language, we can say that by the induction assumption, 
 $$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{k}+\frac{1}{k+1}\le \frac{k}{2}+1+\frac{1}{k+1}.$$
We will be finished if we can show that 
$$\frac{k}{2}+1+\frac{1}{k+1}\le \frac{k+1}{2}+1.$$
This is equivalent to showing that
$$\frac{k}{2}+1+\frac{1}{k+1}\le \frac{k}{2}+\frac{1}{2}+1.$$
The two sides are very similar. We only need to show that
$$\frac{1}{k+1}\le \frac{1}{2}.$$
This is obvious, since $k\ge 1$. 
We have proved the induction step. The base step $n=1$ was obvious, so we are finished. 
A: How rigorous does your proof have to be? You don't need induction/perturbation to prove it. You can notice that your inequality is the same as 
$$
\frac{1}{2}+\frac{1}{3}+\ldots +\frac{1}{n} <\frac{1}{2}+\frac{1}{2}+ \ldots +\frac{1}{2}=\frac{n}{2} \ \forall \ n \ \geq \ 2
$$
It is event easier if you notice that 
$$
1+\frac{1}{2} +\ldots +\frac{1}{n} =H_n = O( \log n) \subseteq O(n) 
$$
since $\frac{n}{2}+1=O(n)$
A: I'm not sure what you expect exactly, but here is how I would do the inequality you mention. 
We start with the base step (as it is usually called); the important point is that induction is a process where you show that if some property holds for a number, it holds for the next. First step is to prove it holds for the first number. So, in this case, $n=1$ and the inequality reads
$$
1<\frac12+1,
$$
which obviously holds. 
Now we assume the inductive hypothesis, in this case that 
$$
1+\frac12+\cdots+\frac1n<\frac{n}2+1,
$$
and we try to use this information to prove it for $n+1$. Then we have
$$
1+\frac12+\cdots+\frac1n+\frac1{n+1}=\left(1+\frac12+\cdots+\frac1n\right)+\frac1{n+1}.
$$
I inserted the brackets to show that we have the sum we know about, through the inductive hypothesis: so
$$
1+\frac12+\cdots+\frac1n+\frac1{n+1}<\frac{n}2+1+\frac1{n+1}.
$$
Now comes the nontrivial part (though not hard in this case), where we need to somehow get $(n+1)/2+1$. Note that this is equal to $n/2+1$ (which we already have) plus $1/2$. And this suggests the proof: as $n\geq1$, $1/(n+1)\leq1/2$. So 
$$
1+\frac12+\cdots+\frac1n+\frac1{n+1}<\frac{n}2+1+\frac1{n+1}\leq\frac{n}2+1+\frac12=\frac{n+1}2+1.
$$
So, assuming the inequality holds for $n$, we have shown it holds for $n+1$. So, by induction, the inequality holds for all $n$. 
A: I see this post is old, but I answer it in case another one has the same problem.
If you have to prove $$1 + 3 + 5 + \cdots + (2n-1) = n^2\tag{*}$$  it is enough to find the LHS of the previous equation in the LHS of $$1 + 3 + 5 + \cdots + (2n-1) + (2(n+1)-1)= (n+1)^2\tag{**}$$The next step is assuming the first equation is true and replace the RHS of (*) in LHS of (**) to obtain $$n^2+(2(n+1)-1)=n^2+2n+1$$ Algebraically, it simplifies as $$n^2+2n+1=n^2+2n+1$$ which proves the first statement.
If you have to prove an inequality holds, the trick is to find what you have on each side of (n) assumption on each side of (n+1)  assumption.
In the induction step of your example, you have $$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{k}+\frac{1}{k+1}\le\frac{k+1}{2}+1\tag{1}$$
Which can be organized as $$(\frac{1}{k+1})+(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{k})\le(\frac{k}{2}+1)+\frac{1}{2}\tag{2}$$
I did not add anything, I just reorganized each side of the inequality to show that the statement $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{k} \leq \frac{k}{2} + 1$ is contained in (1).
Now, if I assume that $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \leq \frac{n}{2} + 1$ is true, then (2) must be true since $\frac{1}{k+2}\leq\frac{1}{2}$ for every positive integer.
