1
$\begingroup$

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..

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steve D Nov 1 '17 at 5:42
  • $\begingroup$ @SteveD If the LHS is already increasing (we assumed that) do we really need to multiply by RHS by that as well? $\endgroup$ – bigfocalchord Nov 1 '17 at 5:43
  • $\begingroup$ Isn’t it easier to show $n!>2^n$, which is also true, more straightforward to show, and implies the desired result? $\endgroup$ – G Tony Jacobs Nov 2 '17 at 0:39
4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ What does both being even mean you can add one to both sides? I still don't get that :( $\endgroup$ – bigfocalchord Nov 1 '17 at 5:59
  • 1
    $\begingroup$ @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 $\endgroup$ – ℋolo Nov 1 '17 at 6:02
  • $\begingroup$ Ahh that makes perfect sense! Thanks! $\endgroup$ – bigfocalchord Nov 1 '17 at 6:03
5
$\begingroup$

\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$.

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

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.