The other day i was trying to prove for $n \geq 1$ that $\ln(1+1/n) < 1/n$. This is a well-know inequality which has many different proof but this is not the point of this question. Here is my work :

  • Base case $n=1$ : $\ln(2) < 1$. True
  • Inductive step, assuming true up to $n$, then : $$ \ln\left(1+\frac{1}{n+1}\right) = \ln\left(\left(1+\frac{1}{n}\right) \left(\frac{1+\frac{1}{n+1}}{1+\frac1n} \right) \right) = \ln\left( 1+\frac{1}{n}\right) + \ln\left(\frac{1+\frac{1}{n+1}}{1+\frac1n} \right) $$ Now applying the inductive hypothesis : $$ < \frac1n + \ln\left(\frac{1+\frac{1}{n+1}}{1+\frac1n} \right) \tag{1} $$ And game over... We need to show that $(1)$ is $< \frac{1}{n+1}$ however Mathematica tells me that this is wrong for positive $n$.

Why does this happen ? I can understand that such proof could fail if I used other non-sharp inequalities on my way to prove the inductive step but here the only inequality, which is obviously the place where this proof fails, is the inductive hypothesis. This means that the inductive assumption is not sharp enough to prove the statement ? Could you give me some insight on why this doesn't work ? Are there any "famous" example where such proof fails ? Or is Mathematica wrong ?

Thanks for your time :)

  • 4
    $\begingroup$ Basically the same happens when you want to try to prove $\frac{1}{n}>0$ by induction. As you said correctly: You lose too much information when you use the induction hypothesis. $\endgroup$ – MooS Mar 22 '17 at 10:28
  • 2
    $\begingroup$ A standard example is the following: proving that $\sum_{n=1}^N \frac1{n^2}$ is less than $2$ for any $N$ is impossible by direct application of induction. You have to show something stronger, like that it's less than $2-\frac1N$, for instance. $\endgroup$ – Arthur Mar 22 '17 at 10:29
  • $\begingroup$ could you prove that the functions are decreasing, prove the inequality at n=1, compare the derivatives of the two sides? $\endgroup$ – Cato Mar 22 '17 at 10:34
  • $\begingroup$ @Cato Comparing the derivatives is just the continuous version of induction...The issue is that you cannot prove $a_n < C$ by induction if $a_n$ is increasing. The sole information $a_n < C$ can never yield $a_{n+1}<C$. $\endgroup$ – MooS Mar 22 '17 at 10:38
  • $\begingroup$ Thank's for your comments/answers ! I never encountered such a case when doing proof by induction. $\endgroup$ – Zubzub Mar 22 '17 at 12:52

It happens because

$ln(1+{1 \over n}) \le {1 \over n}$

is not an implication of the preceding $1,...,n-1$ cases.

It is not your inductive assumption not-sharp enough, it is the target inequity not covered with prediction by the growing set 1,..,n,n+1.

Generally induction method starts as attempt to prove: its success is a proof, its non-success is unrelated to the validity of the proposition.


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.