Question

Prove that 2^n> n+1 such that n is a natural number

Answer 1

I can understand this completely but I have no clue how to explain it mathematically

Answer 2

do you know of mathematical induction?

Answer 3

no

Answer 4

can I just like sub in numbers haha

Answer 5

2^n > n +1

Let us try the base case when n = 2:
2^2 = 4 and n + 1 = 2 + 1 = 3
4 > 3 and therefore it is true for n = 2.

Now assume the statement 2^n > n + 1 is true for ALL n > 1.
Multiply both sides by 2
2 * 2^n > 2(n + 1)
2^(n+1) > 2n + 2 = n + n + 2 > n + 2

So we started with the assumption 2^n > n + 1 for any n > 1 and proved that IF it is true for n, it is true for n+1.

Therefore, it is true for ALL n > 1.

Answer 6

eh that won't work! not legitimate in math to prove that way
and it could work for some numbers only ( well in this case it will for for any natural number n) but some cases no

Answer 7

that's induction! she said she doesn't know about it
which made me think why they would ask that of her? hhhhh

Answer 8

i think only mathematical induction solves this!

Answer 9

2^(n+1) > 2n + 2 = n + n + 2 > n + 2
how exactly does it go to n+n+2?
From my notes so far he wanted us to prove from contradiction and by direct proofs.
Is this the same as direct?

Answer 10

I meant to say: Now assume the statement 2^n > n + 1 is true for some n.


(We then proved that if it is true for n, it is true for n+1 which means it covers all natural number n > 1.)

Answer 11

2n = n + n

Answer 12

No. This is proof by induction.

Answer 13

that's what i'm saying?!

Answer 14

"he wanted us to prove from contradiction and by direct proofs."

You should include such conditions when you post the problem so people know what kind of proof is expected.

Answer 15

True!

Answer 16

I didn't realize, that's just what I have in my notes. It doesn't say which way. I don't know all the ways so I wouldn't have known..
but thanks anyways, I'll try to understand it.

Answer 17

well to prove this you need to have some knowledge about
methods of proving! like induction, contradiction, direct proof like @aum mentioned

Answer 18

As previously stated I didn't have a clue how to do this lol asked for someone to help explain it. Thanks!

Answer 19

Here is the same proof by induction but I am using the variable k for clarification:

2^n > n + 1 ---- (1)

Let us try the base case when n = 2:
2^n = 2^2 = 4 and n + 1 = 2 + 1 = 3
4 > 3 and therefore (1) is true for n = 2.

Now assume the statement 2^n > n + 1 is true for some natural number k. That is,
2^k > k + 1
Multiply both sides by 2
2 * 2^k > 2(k + 1)
2^(k+1) > 2k + 2 = k + k + 2 > k + 2 = (k + 1) + 1

Therefore, IF 2^k > k + 1, then we have proved
2^(k+1) > (k+1) + 1 (it is like replacing k by k+1 above).

Therefore, by induction, it is true for ALL k > 1 and hence for all n > 1.

Answer 20

I'm really confused by the same line
2^(k+1) > 2k + 2 = k + k + 2 > k + 2 = (k + 1) + 1
I get that 2k+2= k+k+2 but then where is k+2 coming from? and why does it = (k+1) +1
I'm just not following :(

Answer 21

2^k > k + 1 ----- (1)
We are starting with the assumption that 2^k > k + 1 is true.
The way the proof of induction works is, that if you assume something is true for k, you will have to prove it is ALSO TRUE for k + 1. To see what we are trying to prove, replace k by (k+1) in (1). We get: 2^(k+1) > (k + 1) + 1. This is what we have to prove.

Clear so far?

Answer 22

oooooh okay hold on

Answer 23

Okay that part is clear. I'm clearly new to the whole proving thing and I can't wrap it around my brain how this proves anything.
Like to me this looks like you're just saying 2^k>k+1 because 2^(k+1)> (k+1)+1

Answer 24

How does it explain it I guess is what I'm asking

Answer 25

We start with 2^k > k + 1.
We then manipulate this inequality by allowed mathematical operations such as addition, subtraction, division, multiplication, law of exponents, logarithms, etc. to prove 2^(k+1) > (k+1) + 1.

Answer 26

wait is it because it's multiplied by 2?

Answer 27

Okay thank you so much!!!!

Answer 28

Is the whole proof clear now?

Answer 29

Yes!

Answer 30

Alright!

Answer 31

And to retrace the steps, we started with the base case of n = 2, calculated the left hand side, calculated the right hand side and proved LHS > RHS. This is the base case proved by direct substitution.

Then we said assume the inequality is true for k. We then manipulated this inequality and proved that if it is true for k it is also true for k+1.

We now say, we proved initially for n = 2. Therefore, it is true for n = 3.
And since it is true for n = 3, it is also true for n = 4
and so on and so forth for all n.

This is induction.

Answer 32

Are most proofs proved by induction?

Answer 33

Not really. But there are certain problems for which induction proof works very well. Type induction proof or proof by induction into YouTube or Google and see a few more examples and it will become clear how this method works.

Answer 34

ok, thank you

Answer 35

You are welcome.

Answer 36

Prove that 2^n > n+1 such that n is a natural number.

A direct proof is also possible. We need to prove \(\large 2^n - 1 > n\) ---- (1)

Consider the first "n" terms of a geometric series that starts with 1 and has a common ratio of 2: 1 + 2 + 2^2 + 2^3 + ...... + 2^(n-1).
The sum of the first n terms of such a geometric series is: \(\large 1.\frac{2^n-1}{2-1} = 2^n -1\)
This is the LHS of (1).
The RHS is n which is sum of the first n terms of the series: 1 + 1 + 1 + ..... (n times).

For n > 1, it is clear that

1 + 2 + 2^2 + 2^3 + ..... > 1 + 1 + 1 + ....... or \(\large 2^n - 1 > n\)

Thus, \(\large 2^n > n + 1\)