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?

  • $\begingroup$ 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$. $\endgroup$ – Patrick Li Nov 25 '12 at 4:42

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.

  • $\begingroup$ 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? $\endgroup$ – Zol Tun Kul Nov 25 '12 at 6:25
  • $\begingroup$ @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. $\endgroup$ – 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)$

  • 1
    $\begingroup$ 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! $\endgroup$ – Zol Tun Kul Nov 25 '12 at 6:28
  • $\begingroup$ You are welcome $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.