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

Relevance

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

• 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

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
• Anonymous

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.

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