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 :)
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.