# 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:

Can you give me a more in depth explanation of the whole procedure?

-
It's similar to proof of equality. The inequality holds for $n = 1$. Suppose it is true for $n$ and you need to prove it is satisfied for $n+1$. –  Patrick Li Nov 25 '12 at 4:42

## 3 Answers

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.

-
Ah! I would have never seen that induction step procedure like that. Awesome thinking - thank you! Question: is this induction step some kind of "standard" or are all exercises of this kind significantly different? –  Zol Tun Kul Nov 25 '12 at 6:25
@Omega: I think of it as standard. I wrote down the formula for "holds at $n=k$." This was $(1)$. Mechanical, we can always do that. Then wrote down formula for "holds at $k+1$. This was $(2)$, mechanical. Then I looked for something in $(1)$ that would help prove $(2)$. This part is not quite mechanical, but the $1+\cdots+\frac{1}{k}$ part of $(2)$ is kind of saying "use what $(1)$ tells you about me." Finally, we had to do the last part, showing that $\frac{k}{2}+1+\frac{1}{k+1}\le \frac{k+1}{2}+1$. This was the only part that was a bit different from the inductions you have done. –  André Nicolas Nov 25 '12 at 9:37

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)$

-
Well, given it is a book exercise in a chapter about induction, I'd like to approach it with induction either way. But thanks for the great idea! –  Zol Tun Kul Nov 25 '12 at 6:28
You are welcome –  Alex Nov 26 '12 at 3:29

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$.

-