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?
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.
No comments:
Post a Comment