I had this problem: Is it always necessary to go from n to (n + 1) or from (n - 1) to n in the inductive hypothesis? Is the "direction" always important?
Here is my solution to one such proof, which turns out to be totally wrong. Is it really so?
$\underline{\textrm{BS}}.$ for n = 1
$\binom{2\cdot 1}{1} = 2 = \frac{4^1}{2 \sqrt{1}}$ It`s ok!
$\underline{\textrm{IH}}.$ for n+1
Assumed $$\binom{2(n+1)}{n+1} \ge \frac{4^{n+1}}{2 \sqrt{n+1}}$$.
$\underline{\textrm{IS}}.$ Prove for n
$$\binom{2n}{n} \ge \frac{4^{n}}{2 \sqrt{n}}$$
$\binom{2n}{n} = \frac{(2n)!}{n!(2n-n)!}=\frac{2!n!}{n!n!}= \frac{2}{n!}$\
First it applies:\ $$\frac{2}{n!} \ge \frac{2}{(n + 1)!} \ \ \ \ \ \ \ \ \textcircled{1}$$\ Clear, because $(n+1)! > n!$\
$$\frac{4^{n+1}}{2 \sqrt{n+1}} \ge \frac{4^{n}}{2 \sqrt{n}} \textcircled{2}$$\ $$\iff \frac{4^{n+1}}{4^n}\geq \frac{\sqrt{n+1}}{\sqrt{n}}$$\ $$\iff 4\geq\sqrt{\frac{n+1}{n}}=\sqrt{1+\frac{1}{n}}$$\
Since $\frac{1}{n} \to 0$ (monotonically decreasing)$ \implies \sqrt{1+\frac{1}{n}} = 2$ for n = 1 and $\sqrt{1+\frac{1}{n}} = 1$ for $n \to \infty$, that's why the inequality \textcircled{2} always holds.
Then through Induction Hypothesis(IH) I get:
$$\frac{2}{n!} \overset{\textcircled{1}}{\ge} \frac{2}{(n + 1)!} \overset{IH}{\ge} \frac{4^{n+1}}{2 \sqrt{n+1}}\overset{\textcircled{2}}{\ge} \frac{4^{n}}{2 \sqrt{n}}$$ $$\iff \binom{2n}{n}\ge \binom{2(n + 1)}{n+1} \ge \frac{4^{n+1}}{2 \sqrt{n+1}}\ge \frac{4^{n}}{2 \sqrt{n}}$$
From there applies $$\binom{2n}{n}\ge \frac{4^{n}}{2 \sqrt{n}}$$
Yes, this is wrong. The idea of induction is like a row of dominos. If the first falls, then the one behind must fall to. But what you prove is that if the second falls then the first falls. But you can't prove that the second falls.
There is a variant of induction that can be used:
Adding the third step will complete this proof.