2
$\begingroup$

While looking at some examples of proof by induction related to inequalities, I had this one that I didn't quite get:

Prove by induction that the following holds for all $n \ge 1$:

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}\le\frac{n}{2}+1$$


We have to prove that it holds for $n + 1$, that is:

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}+\frac{1}{n + 1}\le\frac{n > + 1}{2}+1$$


Hypothesis:

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}\le\frac{n}{2}+1$$


To prove this, we have to prove two things:

$$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}+\frac{1}{n+1}\le\frac{n}{2}+1+\frac{1}{n+1}$$

$$\textrm{and}$$

$$\frac{n}{2}+1+\frac{1}{n+1}\le \frac{n + 1}{2}+1$$


$$\textrm{* Proof goes here *}$$

My problem is with the "we have to prove these two things" part. I can see how proving them would effectively prove the whole thing, since we're trying to prove that $A \le C$, it would be the same as proving that $A \le B \land B \le C$, which seems to be what they are doing. However, under what reasoning did they decide that $B$ should be $\frac{n}{2}+1+\frac{1}{n+1}$? Was that the value necessary for $B$, or could it have been something else?

$\endgroup$
  • $\begingroup$ The value of $B$ is followed by hypothesis $\endgroup$ – Shuchang Dec 3 '13 at 1:50
  • $\begingroup$ The induction hypothesis says that the sum up to $1/n$ is $\le n/2 +1$. So the sum up to $1/(n+1)$ is $\le n/2+1 +1/(n+1)$. And of course this is $\le (n+1)/2+1$, since $1/(n+1)\le 1/2$. $\endgroup$ – André Nicolas Dec 3 '13 at 1:51
  • 1
    $\begingroup$ It could have been something else, perhaps, but they chose that value because it fit their own version of the proof the best. $\endgroup$ – Joe Z. Dec 3 '13 at 1:52
  • 1
    $\begingroup$ ?? Haven't they simply added 1/n+1 to both sides of the hypothesis statement. Why is it so magical to you? $\endgroup$ – TenaliRaman Dec 3 '13 at 2:12
  • $\begingroup$ @TenaliRaman: I know what they did, I don't know why, of all options, they had to choose that one. They could've added something else to both sides too, right? Why not? $\endgroup$ – Zol Tun Kul Dec 3 '13 at 3:02
2
$\begingroup$

It is probably better to read that as "to prove this using the method below, we have to prove two things...."

Using a proof method that starts by proving that particular $A \leq B$ is a fairly natural choice in this particular instance, since it follows trivially from the inductive hypothesis, and the right hand side appears simpler than the left hand side.

$\endgroup$
2
$\begingroup$

First, check the base case $n = 1$ (trivial). Then for the inductive step, assume that the statement holds for $n = k$, that is, assume $H_k \leq k/2 + 1$, where $H_k$ is the $k$th harmonic number. Then use the inductive hypothesis to prove that $H_n \leq n/2 + 1$ also holds for $n = k + 1$. In other words, $$H_k + \frac{1}{k + 1} \leq \frac{k + 1}{2} + 1$$ is the inequality you need to prove. But this is equivalent to the first "thing" by the inductive hypothesis: just add $1/(k + 1)$ to both sides of $$H_k \leq \frac{k}{2} + 1.$$ Now you simply need to prove the second "thing" i.e. $B \leq C$ with $B = k/2 + 1 + 1/(k + 1)$ and $C = (k + 1)/2 + 1$ and you are done.

$\endgroup$
  • $\begingroup$ It would be better for showing what B is. :) $\endgroup$ – user39843 Dec 3 '13 at 2:15

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.