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

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