How would you prove that 2^n > n?

I'm having a few problems going through this exercise even though it's kinda easy. I have to use mathematical induction to prove that 2 ^ n > n.

6 Answers

Relevance
  • 1 decade ago
    Favourite answer

    Good answer Puggy.

    And of course it holds for all negative numbers too, because

    0 < 2 ^ n < 1, for n < 0, and therefore 2 ^ n < n.

  • Anonymous
    4 years ago

    N 2 N

  • Puggy
    Lv 7
    1 decade ago

    If induction is involved, I'm assuming you mean for all natural numbers n. Let's start with the base case of n = 1.

    If n = 1, then 2^n = 2^1 = 2, and

    n = 1, so LHS > RHS and the inequality holds true for n = 1.

    For our induction hypothesis, we assume 2^k > k for some k > 1.

    (We want to prove that 2^(k + 1) > (k + 1) )

    However,

    2^(k + 1) = (2^k)(2^1)

    = (2^k)(2)

    which, by our induction hypothesis, is

    > k(2)

    = 2k

    = k + k

    And since k > 1

    > k + 1

    Showing that

    2^(k + 1) > k + 1

    Confusing? Here's the entire chain all over again.

    2^(k + 1) = 2*(2^k) > 2*(k) = k + k > k + 1

    So

    2^(k + 1) > (k + 1)

    Which means the inequality holds true for n = k + 1.

    Thus by the Principal of Mathematical Induction,

    2^n > n for all natural numbers n.

  • Anonymous
    5 years ago

    This Site Might Help You.

    RE:

    How would you prove that 2^n > n?

    I'm having a few problems going through this exercise even though it's kinda easy. I have to use mathematical induction to prove that 2 ^ n > n.

    Source(s): prove 2 n: https://biturl.im/QdG2L
  • What do you think of the answers? You can sign in to give your opinion on the answer.
  • Anonymous
    1 decade ago

    Let P(n) be 2^n>n, then

    P(1): 2>1 is true.

    Assume that P(k) is true for +ve integer k>1, then

    2^(k+1)-(k+1)=2*2^k-k-1=

    2^k-k+2^k-1>0=>

    P(k+1): 2^(k+1)>(k+1) is true.

    So, the statement P(n) is true for any +ve integer n.

    Mistake: next time, you should specify what n is first.

  • 1 decade ago

    Assume the statement is true for n=k

    Therefore, 2^k > k

    Now prove it is true for n=k+1

    2^k+1 > k+1?

    2^k × 2^1 > k+1?

    2^k × 2 > k+1 (we had assumed that it is true for n=k, so this is true)

    Therefore, if the statement is true for n=k, it is also true for n=k+1

    Is it true for n=1?

    2¹ > 1? Yes, 2>1

    So the statement is true.

Still have questions? Get answers by asking now.