Proof of $n!\geq2^{n-1}$ by mathematical induction

Question

I am trying to make a proof

$$n!\geq2^{n-1}\;\;\forall \;n\in N$$

Here's what I've done!

$ \text{When}\;\; n=1,\;\; 2^{0}\leq 1!$,

$ \text{when}\;\; n=2,\;\; 2^{1}\leq 2!$,

$ \text{when}\;\; n=3,\;\; 2^{2}\leq 3!$,

$\vdots$

Assume it is true for $n=k$, then

$$2^{k-1}\leq k!$$.

Now, we want to prove for $n=k+1$.

I got stuck at this point. I need help! Thanks!

Answer 1

Then for $n = k+1$, we have $$2^k = 2\cdot2^{k-1} \le 2 \cdot k!\ \text{ by inductive argument}$$ From here, it is easy to see that $2\cdot k! \le (k+1)k! = (k+1)!$

Answer 2

\begin{align} (k+1)! &= k!(k+1) \\ &\ge2^{k-1}(k+1) \end{align}

Can you complete it?

Answer 3

You're off by $1$ in your basis observations; you should have, instead, the following:

$$ 1! \geq 2^0 \\ 2! \geq 2^1 \\ 3! \geq 2^2 $$

For the induction step, you should be thinking like this:

$$ 2^k = 2 \times 2^{k-1} \leq \cdots $$

Can you complete that line?

---

P.S. Siong Thye Goh's answer gives the other half... :-)

Answer 4

If $n=1$, we have $1!=1\ge 1= 2^0$.

Suppose that $n!\ge 2^{n-1}$ for some $n\ge1$.

Then $$(n+1)! = (n+1)\cdot n! \ge 2\cdot n! \ge 2\cdot 2^{n-1} = 2^n$$

So, by induction, $n!\ge 2^{n-1}$, for all $n\in\mathbb{N}$.