6
$\begingroup$

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?

  • 0
    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$.2012-11-25

3 Answers 3

9

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.

  • 0
    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?2012-11-25
  • 0
    @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.2012-11-25
2

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
    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!2012-11-25
  • 0
    You are welcome2012-11-26
1

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