2
$\begingroup$

This question already has an answer here:

Im trying to solve the following question


enter image description here


In the second step where do they get $k!=2^k-1?$

$\endgroup$

marked as duplicate by GNUSupporter 8964民主女神 地下教會, Hans Engler, B. Mehta, HK Lee, Chris Custer May 11 '18 at 10:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ They never wrote $k! = 2^k - 1$, or even $k!=2^{k-1}$. They only used the induction hypothesis $k!\geq 2^{k-1}$. $\endgroup$ – 5xum Sep 17 '15 at 5:51
  • $\begingroup$ They wrote $k! = 2^{k-1}$, which is the induction hypothesis. $\endgroup$ – Christopher Carl Heckman Sep 17 '15 at 5:52
  • 1
    $\begingroup$ @Yash Malik can you fix your edit please $\endgroup$ – techno Sep 17 '15 at 6:06
  • 1
    $\begingroup$ @Yash Malik With due respect,Please stop editing if you dont know what you are doing. $\endgroup$ – techno Sep 17 '15 at 6:15
  • 1
    $\begingroup$ @YashMalik Thanks :) its okay now.No probs. $\endgroup$ – techno Sep 17 '15 at 6:17
1
$\begingroup$

In the induction step, they say "Suppose that $k! \ge 2^{k-1}$ for some $k \ge 1$."

That then allows them to say "$(k+1)\,k! \ge (k+1)\,2^{k-1}$", multiplying both sides of the inequality by the positive $(k+1)$.

$\endgroup$
  • $\begingroup$ @Henry Do you think you could correct the mess there? $\endgroup$ – Did Sep 17 '15 at 8:40
1
$\begingroup$

Consider this example...similar to your problem..

Prove $n!>2^n$ $(n \geq4)$ Prove it at first for any $n \geq 4$.

Assume it true for some $k$. let it be true $k!>2^k$

Now we try to prove it true for $k+1$. We have to prove $(k+1)!>2^{k+1}$.

We know $2^{k+1}$=$2^k*2$.

Also,we know $(k+1)!=k!*(k+1).$ We also assumed earlier $k!>2^k$.

So, we can write $k!(k+1)>2^k*2$ [Since,$k>4 ,k+1>4>2$ which is in the RHS and $k!>2^k$ as we assumed earlier].

Hope this helps you to understand the problem and solve it in a similar way.

$\endgroup$
  • $\begingroup$ @techno-Welcome!!Hope this helps you!!. $\endgroup$ – tatan Sep 17 '15 at 6:52
  • $\begingroup$ @techno-Please upvote if it helps :-)! $\endgroup$ – tatan Sep 17 '15 at 7:00

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