# Induction proof of $\ln(1+1/n) \leq 1/n$ fails even though it is true

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 ?

• 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. – MooS Mar 22 '17 at 10:28
• 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. – Arthur Mar 22 '17 at 10:29
• could you prove that the functions are decreasing, prove the inequality at n=1, compare the derivatives of the two sides? – Cato Mar 22 '17 at 10:34
• @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$. – MooS Mar 22 '17 at 10:38
• Thank's for your comments/answers ! I never encountered such a case when doing proof by induction. – Zubzub Mar 22 '17 at 12:52

$ln(1+{1 \over n}) \le {1 \over n}$
is not an implication of the preceding $1,...,n-1$ cases.