4

Prove by induction that: $2^n \le (n+1)! \ \ \ \ \ \ \ \ \forall n\in\mathbb{N}$

I tried to solve in this way: $$P(1): 2 \le 2! \quad\text{(true)}$$ $$P(n) \implies p(n+1), \;\text{ where }\;\; p(n+1): 2^{n+1} \le (n+2)!$$ so $$2^n \le (n+1)! \\ 2^n \cdot 2\le 2 \cdot (n+1)! \\ (n+1)! \cdot 2 \le 2 \cdot (n+1)! \quad\text{(true)}$$ where tapped that $2^n \le (n+1)!$

Are my steps right?

Angelo
  • 12,328
Loris Simonetti
  • 567

3 Answers3

3

It's a bit confusing: the base case is correct but I don't think you have proved the inductive step, the inequality that you seek to prove in that case is never reached in the steps you have written.

A more streamlined approach for the inductive step would be the following:

$$(n+2)!=(n+2)(n+1)!\geq (n+2) 2^n\geq 2\cdot 2^n=2^{n+1}$$

where in the first equality we used the definition of factorial, in the first inequality the inductive hypothesis and in the second inequality the fact that $n+2\geq 2\ (n\geq 0) $

lorenzo
  • 4,032
2

There's a few things wrong with this:

  • Your conclusion should be that $2^{n+1} \le (n + 2)!$, i.e. $P(n + 1)$. This conclusion should at least appear somewhere in the argument (preferably at the end of it!), or else you haven't completed the induction step.
  • Ending your argument with "... therefore we get this, which is clearly a true statement" is the fallacy of affirming the consequent. You should start with the statements you know (or are assuming) to be true, and ending with the statement you want to show is true. Ending with a true statement tells you nothing.
  • When you shift from $2^n \cdot 2 \le 2 \cdot (n + 1)!$ to $(n + 1)! \cdot 2 \le 2 \cdot (n + 1)!$, you appear to be substituting $2^n$ with the presumed larger quantity $(n + 1)!$. In the former inequality, $2^n$ is the smaller quantity. You are allowed to replace it with an even smaller quantity, but replacing it with a larger quantity is a crapshoot. For example, $3 \le 7$, and $3 \le 8$, but this doesn't mean that $8 \le 7$.
Theo Bendit
  • 50,900
0

After you get $2^{n+1}\le 2(n+1)!$.......(1)

Proceed as follows:

$(n+1)!=(n+1)!$

$\implies \color{red}{(1+1)}(n+1)!\le \color{green}{(n+2)}(n+1)!$

$(\because (1+1)<(n+2)\forall n\in\mathbb N$)

$\implies 2(n+1)!\le (n+2)!$.........(2)

From (1) and (2), you have $2^{n+1}\le (n+2)!$

Nitin Uniyal
  • 7,946