Question

prove that 2^n>n for every n
with mathematical induction

Answer 1

First, you must have a value of n for which the inequality is obviously true.
Can you name that n?

Answer 2

the initial value of n
n=1 => 2^1>1=>2>1 so its true for the initial value of n

Answer 3

then we suppose that the property is true for n=k
so 2^k>k

Answer 4

This is going really well!

Answer 5

now i am stuck in the first step
for n=k+1
2^(k+1)>(k+1)

Answer 6

OK, can you write 2^(k+1) in another way?

Answer 7

Consider: \[
2^k > k \implies 2^k+2^k > k + k
\]

Answer 8

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

Answer 9

Hey @wio, why are you giving it away?

Answer 10

I haven't given it away.

Answer 11

If you say so...

Ok, so now you have 2^(k+1) = 2 x 2^k.
You know something about 2^k...

Answer 12

2^k>k

Answer 13

Yes, so 2^(k+1)=2x2^k > 2k

Answer 14

yes

Answer 15

now i have to prove that 2k>k+1?

Answer 16

2k=k+k, so 2^(k+1)=2x2^k > 2k = k + k.

What do you have to prove in this step?

Answer 17

that k+k>k+1?

Answer 18

You have to prove that 2^(k+1)> k+1.
You have proven: 2^(k+1)> k+k.

I think we're done, because k+k > k+1, if k > 1. This is OK, because the case k=1 is not interesting (it was the initial step)

So you have proven the inequality for n=k+1. Because the inequality is true for n=1, it is now true for n=1+1=2, for n=2+1=3 and so on.

Answer 19

No, \(k \not > 1\). \(k\geq 1\). If you ignore \(k=1\) then the \(k=2\) case needs to be proven independently, because you fail to prove \(p(2)\) and thus \(p(2)\implies p(3)\) is not sufficient to prove \(p(3)\) and so on.

Answer 20

@wio is right.
Taking k=1 into account, we have proven:

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

So if you compare the leftmost term with the rightmost you have 2^(k+1) > k+1.
Now we're done.