# Prove $n! > 2^n-1$ for $n \geq 4$

Prove $n! > 2^n-1$ for $n \geq 4$

Base Case - $(n=4)$ $\implies$ $24 >15$

Assume true for $n=k$ $\implies$ $$k! > 2^k -1$$ $$(k+1)k! > 2^k-1$$ $$(k+1)! > 2^{k}-1$$ $$2(k+1)! > 2^{k+1}-2$$ $$2(k+1)! > (2^{k+1}-1)-1$$

I'm not sure how to continue now..

• When you multiply the left side by $k+1$, also multiply the right side by $k+1$. Then use that $k+1>2$. Finally, use that $(k+1)!$ is even, while $2^{k+1}-1$ is odd. – Steve D Nov 1 '17 at 5:42
• @SteveD If the LHS is already increasing (we assumed that) do we really need to multiply by RHS by that as well? – bigfocalchord Nov 1 '17 at 5:43
• Isn’t it easier to show $n!>2^n$, which is also true, more straightforward to show, and implies the desired result? – G Tony Jacobs Nov 2 '17 at 0:39

you didn't had a mistake, but the way is not the right approach:

if you assume it is true for $n=k$ to show it is true for $k+1$ you need to show that:$$(k+1)!\ge2^{k+1}-1\\\text{we can do the following: }(k+1)k!\ge(k+1)\times\left(2^{k}-1\right)\gt2\times\left(2^{k}-1\right)$$ because we assumed that $k!\ge2^k-1$ for $k\ge4$ if we show that $k+1\gt2$(which is true) we get $(k+1)!\gt2^{k+1}-2$ because both are even and $(k+1)!\ne2^{k+1}-2$ i can add one to the right side and i get $$(k+1)!\gt2^{k+1}-1$$and you had shown it is true to $k=4$ thus it is true $\forall k\ge4$

• What does both being even mean you can add one to both sides? I still don't get that :( – bigfocalchord Nov 1 '17 at 5:59
• @dydxx if i have 2 even numbers that are not equal, it means that one is greater than the other by at least 2 right? we know that the right side is less than the left side, so it is less by at least 2, so if i add 1, it will still be less by at least 1 – ℋolo Nov 1 '17 at 6:02
• Ahh that makes perfect sense! Thanks! – bigfocalchord Nov 1 '17 at 6:03

\begin{align} (k+1)k! &> (k+1)(2^k-1)\\ &> 2(2^k-1)\\ &> 2^{k+1}-2 \end{align}

Thus $(k+1)!\ge 2^{k+1}-1$, but the left side is even while the right side is odd, so equality is not an option, and $(k+1)!>2^{k+1}-1$.

• How did u know $(k+1)! > 2^{k+1} - 1$ – bigfocalchord Nov 1 '17 at 5:50
• Let a b be integers if a>b the a>=b-1 – J. Sadek Nov 1 '17 at 5:56

You are making it more difficult than it needs to be. The $n! > 2^n -1$ is in integers the same as $n! \geq 2^n$. This bound is sharper, and you get rid of the annoying $-1$. Notice that the induction step is then simply $$(n+1)! = (n+1) n! \geq 2\cdot 2^n = 2^{n+1 },$$ where we used $n+1\geq 2$ and the induction hypothesis $n! \geq 2^n$.

• How do you get the last inequality? – Guy Fsone Nov 1 '17 at 14:15
• I think there is -1 missing – Guy Fsone Nov 1 '17 at 14:25
• @GuyFsone Where? The point of this answer is to get rid of the $-1$ by replacing $>$ with $\geq$. – Sil Nov 1 '17 at 14:27
• I see thanks just update your post plz – Guy Fsone Nov 1 '17 at 14:31
• I did for you. I know that struggle – Guy Fsone Nov 1 '17 at 14:37