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?
Best Answer
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.