I was able to "prove" by induction that $\forall n \in \mathbb{N} (n\geq 2 \implies n!>2^n)$. Where did I go wrong?

Question

Edit: I have made a mistake when introducing the induction step for the statement. The actual induction step is of the form:

$\forall n((n\geq2 \implies n!>2^n) \implies (n+1\geq2 \implies (n+1)!>2^{n+1}))$

In my "proof", I used the following instead:

$\forall n((n\geq2 \implies n!>2^n) \implies (n\geq2 \implies (n+1)!>2^{n+1}))$

This may or may not affect the actual proof. Maybe with this difference, I won't be able to prove the inductive step anymore. I'll have to give it some more tries. The rest of the answer remains unchanged.

The universe is the set of natural numbers, the smallest being 0. We want to prove that $\forall n\geq4:n!>2^n$. We can prove this by induction by proving the base step and the inductive step.

Base step $4!>2^4$

$24>16$

$true$

Inductive step: (Let's just assume I proved the induction step here, because it's the same in both cases, and irrelevant to my actual problem. I think the inductive step is always true as long as $n>1$, which is also always true because we assumed that $n>=4$)

Now see what happens when I rewrite my problem in the following way

$\forall n:n\geq4 \implies n!>2^n$

If I try to solve this modified expression with induction, by Peano's final axiom of induction, I would have to start with a base case of 0 (or 1, doesn't matter).

$0\geq 4 \implies 0!>2^0$

$false \implies 0!>2^0$

$true$

The problem is, what if I try to prove that the same statement is true for all $n\geq 2$ instead?

In the case of $\forall n\geq2:n!>2^n$, the base case is false, because

$2!>2^2$

$2>4$

$false$

But in the case of $\forall n:n\geq2 \implies n!>2^n$, the base case is still vacuously true for $n=0$, and still proves the inductive step for all $n\geq 2$. However, the statement is undeniably false. So where did I go wrong in my proof?

For the sake of being completely clear, I will include my inductive step of the second statement as well.

$\forall n((n\geq2 \implies n!>2^n) \implies (n\geq2 \implies (n+1)!>2^{n+1}))$

This is the same as saying

$\forall n((n>1 \implies n!>2^n) \implies (n>1 \implies (n+1)!>2^{n+1}))$

By laws of propositional logic, this statement is equivalent with the following:

$\forall n(n>1 \land n!>2^n \implies (n+1)!>2^{n+1})$

$\forall n(n>1 \land n!>2^n \implies (n+1)\cdot n!>2\cdot 2^n)$

$\forall n(n>1 \land n!>2^n \implies n!>2\cdot 2^n/(n+1))$

The upper statement is implied by the one below:

$\forall n(n>1 \land n!>2^n \implies n!>2^n\land 2^n>2\cdot 2^n/(n+1))$

$\forall n(n>1 \land n!>2^n \implies true \land 1>2/(n+1))$

$\forall n(n>1 \land n!>2^n \implies n+1>2)$

$\forall n(n>1 \land n!>2^n \implies n>1)$

$true$

So where did my "proof" go wrong?

Answer 1

(Let's just assume I proved the induction step here, because it's the same in both cases, and irrelevant to my actual problem.)

It's a shame you said this, because the details of the induction step are totally going to matter for your actual problem.

The reason is that when you do the induction step, attempting to prove $\forall n: (P(n) \implies P(n+1))$, the induction hypothesis you are allowed to start with will change each time you change the statement you are trying to prove by induction.

• When you try to prove $\forall n \geq 4: n! > 2^n$ your induction hypothesis is of the form is of the form $n! > 2^n$ and the proof is a mechanical calculation.
• When you try to prove $\forall n: (n \geq 4 \implies n! > 2^n)$ your induction hypothesis is of the form $(n \geq 4 \implies n! > 2^n)$. The induction step with this assumption works when $n \geq 4$ (the premise of the implication is true, so you get the inequality $n! > 2^n$ and can do the calculation as before) and when $n \leq 2$ (the statement for $n+1$ is a vacuously true implication and can be proved without the hypothesis). But there is a problem when $n = 3$, because the statement at $n$ doesn't give you the inequality but the statement at $n+1$ isn't vacuously true. In fixing this, you end up re-proving the $n=4$ base case.
• When you try to prove $\forall n: (n \geq 2 \implies n! > 2^n)$ your induction hypothesis is of the form $(n \geq 2 \implies n! > 2^n)$. Now you get a problem at $n = 1$: you don't get that the statement is vacuously true for $n+1=2$ and you don't get the inequality from the implication in your hypothesis. When you try to fix it this time, you find that the statement is actually false at the $n=2$ case.