Question

Prove using mathematical induction that 2^n> 2n when n>2

Answer 1

@mathstudent55 @jhonyy9

Answer 2

This is my working
If 2^n >2n then 2^(n+1) - 2 >2n
2^n >= 2^(n+1) - 2
So 2^n >2n

Since when n = 3 2^n > 2n is true so it should be true for other values

Answer 3

jhonyy9, zzr0ck34, and AceSpeedFighter are typing replies...

Answer 4

Suppose \(n=3\) then for sure \(2^n>2n\)

Suppose it is true for \(n\). Then \(2^n>2n\) and since \(n>1\) we have \(2^n*2>2n*2\implies 2^{n+1}>4n=2n+2n>2n+2>2(n+1)\)

Answer 5

so you know that n>2 what mean that you need try it for n=3

2^3 > 2*3
8>6 this is true

rewrite it for n=k

2^k > 2*k suppose is true and now prove it true for k=k+1

for k=k+1 will be

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

2^k *2 > 2k +2 so do you can ending it now ?

Answer 6

k=k+1 makes no sense...

Answer 7

\(\color{#0cbb34}{\text{Originally Posted by}}\) @jhonyy9
so you know that n>2 what mean that you need try it for n=3

2^3 > 2*3
8>6 this is true

rewrite it for n=k

2^k > 2*k suppose is true and now prove it true for k=k+1

for k=k+1 will be

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

2^k *2 > 2k +2 so do you can ending it now ?
\(\color{#0cbb34}{\text{End of Quote}}\)

Thats the part I am having trouble with. What to do now?

Answer 8

You are assuming the conclusion @jhonyy9

Answer 9

\(2^(k+1) > 2*(k+1)
\) is what you are trying to show, and you assumed it to be true. See if you can follow what I did.

Answer 10

\(\color{#0cbb34}{\text{Originally Posted by}}\) @zzr0ck3r
Suppose \(n=3\) then for sure \(2^n>2n\)

Suppose it is true for \(n\). Then \(2^n>2n\) and since \(n>1\) we have \(2^n*2>2n*2\implies 2^{n+1}>4n=2n+2n>2n+2>2(n+1)\)
\(\color{#0cbb34}{\text{End of Quote}}\)
I understand your method. Can please also explain How should I demonstrate it? Like what wordings should I add after each step?

Answer 11

do you know the proof method of math induction ?

Answer 12

First show it is true for n=3

Then assume it is true for some arbitrary \(n>2\)

Then use that assumption to show that it is true for \(n+1\)

Answer 13

Okay one more thing.
What you showed with 2^n+1> 4n is true for n+1 and since we are talking about n, shouldn't this inequality be invalid?

Answer 14

sorry but math induction say accept it true for n=k and prove it for k=k+1

Answer 15

lol k...n same thing. But you are writing k=k+1 and that makes no sense.

Answer 16

k=k+1 implies 1=0

Answer 17

you mean that if it is true for k it must be true for k+1 not k=k+1

Answer 18

Actually it is
n=k
And then we assume n=k+1

Answer 19

if n=k and n=k+1 then 1=0

Answer 20

so again, not true

Answer 21

you have the right ida, but your notation is messed up

Answer 22

Okay one more thing.
What you showed with 2^n+1> 4n is true for n+1 and since we are talking about n, shouldn't this inequality be invalid?

Answer 23

what?

Answer 24

no
i wrote what say the math induction proofe method really

there is first with n than try it for n= 1 but here n>2 so try it for n=3

get it true after this rewrite it for n=k and this suppose that is true

after this prove that is true for k=k+1

these are the steps of math induction - hope i know it right

Answer 25

stop writing k=k+1 this is NEVER true

Answer 26

if k=k+1 subtract k from both sides

Answer 27

Suppose \(n=3\) then for sure \(2^n>2n\)

Suppose it is true for \(n\).
Then \(2^n>2n\) and since \(n>1\) we have
\(2^n*2>2n*2\implies 2^{n+1}>4n=2n+2n>2n+2>2(n+1)\)
Okay but how does this proves that 2^n >2n

Answer 28

what do you get?

Answer 29

sorry you dont understand me zzrock3r

Answer 30

I showed \(2^{n+1}>2(n+1)\) by assumeing \(2^n>2n\). This is induction

Answer 31

or you need relearning what is the math induction proof method

Answer 32

I have a masters in math and I teach induction.

Answer 33

YES exactly. How does that do anything. You showed something else

Answer 34

P.S. I am just new to induction. Dont consider my replies as insults. It's just that I am awfully confused with assumption

Answer 35

@jhonyy9 answer one question for me.

if \(k=k+1\) and you subtract \(k\) from both sides, what do you get?

Answer 36

Mathematical induction can be used to prove that the following statement, which we will call P(n), holds for all natural numbers n.

0 + 1 + 2 + ⋯ + n = n ( n + 1 ) 2 . {\displaystyle 0+1+2+\cdots +n={\frac {n(n+1)}{2}}\,.} 0+1+2+\cdots +n={\frac {n(n+1)}{2}}\,.
P(n) gives a formula for the sum of the natural numbers less than or equal to number n. The proof that P(n) is true for each natural number n proceeds as follows.

Basis: Show that the statement holds for n = 0.
P(0) amounts to the statement:

0 = 0 ⋅ ( 0 + 1 ) 2 . {\displaystyle 0={\frac {0\cdot (0+1)}{2}}\,.} 0={\frac {0\cdot (0+1)}{2}}\,.
In the left-hand side of the equation, the only term is 0, and so the left-hand side is simply equal to 0.
In the right-hand side of the equation, 0·(0 + 1)/2 = 0.
The two sides are equal, so the statement is true for n = 0. Thus it has been shown that P(0) holds.

Inductive step: Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.

Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:

( 0 + 1 + 2 + ⋯ + k ) + ( k + 1 ) = ( k + 1 ) ( ( k + 1 ) + 1 ) 2 . {\displaystyle (0+1+2+\cdots +k)+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.} (0+1+2+\cdots +k)+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.
Using the induction hypothesis that P(k) holds, the left-hand side can be rewritten to:

k ( k + 1 ) 2 + ( k + 1 ) . {\displaystyle {\frac {k(k+1)}{2}}+(k+1)\,.} {\frac {k(k+1)}{2}}+(k+1)\,.
Algebraically:

k ( k + 1 ) 2 + ( k + 1 ) = k ( k + 1 ) + 2 ( k + 1 ) 2 = ( k + 1 ) ( k + 2 ) 2 = ( k + 1 ) ( ( k + 1 ) + 1 ) 2 {\displaystyle {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}\end{aligned}}} {\begin{aligned}{\frac {k(k+1)}{2}}+(k+1)&={\frac {k(k+1)+2(k+1)}{2}}\\&={\frac {(k+1)(k+2)}{2}}\\&={\frac {(k+1)((k+1)+1)}{2}}\end{aligned}}

Answer 37

looke it please from wikipedia.org

Answer 38

To prove induction for some statement P we must show \(p(n)\) implies \(p(n+1)\)

Answer 39

How about you guys clear my confusion then go on a debate

Answer 40

yeah @jhonyy9 show me one place there where they say \(k=k+1\)

Answer 41

I showed \(2^{n+1}>2(n+1)\) by assumeing \(2^n>2n\). This is induction
YES exactly. How does that do anything. You showed something elseP.S. I am just new to induction. Dont consider my replies as insults. It's just that I am awfully confused with assumption

Answer 42

here is

Inductive step: Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.

Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:

Answer 43

You want to show \(2^n>2n\) to do this you must show it is true for \(n=1\) (but in this case \(n=3\)).

Then you must assume it is true for some \(k\) and then show that implies it is true for \(k+1\).

I simply used \(n\) instead of \(k\).

Answer 44

It is just that you multiplied the "assumption" by 2

Answer 45

@jhonyy9 I see no equals sign there....you are wrong man. k=k+1 mkes no mathematical sense

Answer 46

Yes, @FaiqRaees every induction proof uses a different trick, some are hard some are easy

Answer 47

How is this even a trick. It is just multiplication by 2. How does that prove the inequality ._.

Answer 48

Thank God @Kainui is here

Answer 49

I hope that's not sarcasm lol

Answer 50

Assume \(2^k>2k\) for some \(k\).

Multiply both sides by \(2\)

\(2^k*2>2k*2\)

This gives

\(2^{k+1}>2k*2=4k=2k+2k>2k+2=2(k+1)\)

So we have shown \(2^k>2k\implies 2^{k+1}>2(k+1)\)

So by induction \(2^n>2n\) for all \(n\ge 3\)

Answer 51

Of course not

Answer 52

Kainui - please the math induction method not say that try it for n=1 so in this case for n=3

after this than you see it true rewrite it for n=k and this suppose it true and prove it for k=k+1

Answer 53

jhony, stop talking and answer this

if k=k+1 and you subtract k from both sides, what do you get?

Answer 54

@jhonyy9 answer the question I asked.

Answer 55

I am just got here late I'm just trying to figure out like what @FaiqRaees is trying to understand

Answer 56

Assume \(2^k>2k\) for some \(k\).

Multiply both sides by \(2\)

\(2^k*2>2k*2\)

This gives

\(2^{k+1}>2k*2=4k=2k+2k>2k+2=2(k+1)\)

So we have shown \(2^k>2k\implies 2^{k+1}>2(k+1)\)
// This Statement is only true if \(2^k>2k\) is true. How is that going to be proved

So by induction \(2^n>2n\) for all \(n\ge 3\)

Answer 57

what you mean is that if \(P(k)\) is true then \(p(k+1)\) is true... but \(k=k+1\) makes no sense ever in mathematics (unless we are in mod1)

Answer 58

no @FaiqRaees you are not understanding induction.

We showed it was true for n=3

Then we ASSUME it is true for some arbitrary k

Then show THAT gives true for k+1

Answer 59

@Kainui
I want to know what principle are we going to use here to prove the inequality through induction

Answer 60

no @FaiqRaees you are not understanding induction.

We showed it was true for n=3

Then we ASSUME it is true for some arbitrary k

Then show THAT gives true for k+1 /// How do you know it is true for k+1??

Answer 61

you always end up assuming something that looks like the thing we are proving.

But you are proving it for ALL n and we are assumeing it for SOME n

Answer 62

I showed you how assuming it true for some k gives it is true for some k+1

Answer 63

we can assume it is true for some k because we know it is true for 3

Answer 64

zzrock3r do you agree this please

Mathematical induction as an inference rule can be formalized as a second-order axiom. The axiom of induction is, in logical symbols,

∀ P . [ [ P ( 0 ) ∧ ∀ ( k ∈ N ) . [ P ( k ) ⇒ P ( k + 1 ) ] ] ⇒ ∀ ( n ∈ N ) . P ( n ) ] {\displaystyle \forall P.\,[[P(0)\land \forall (k\in \mathbb {N} ).\,[P(k)\Rightarrow P(k+1)]]\Rightarrow \forall (n\in \mathbb {N} ).\,P(n)]} \forall P.\,[[P(0)\land \forall (k\in \mathbb {N} ).\,[P(k)\Rightarrow P(k+1)]]\Rightarrow \forall (n\in \mathbb {N} ).\,P(n)]
where P is any predicate and k and n are both natural numbers.

In words, the basis P(0) and the inductive step (namely, that the inductive hypothesis P(k) implies P(k + 1)) together imply that P(n) for any natural number n. The axiom of induction asserts that the validity of inferring that P(n) holds for any natural number n from the basis and the inductive step.

Answer 65

Okay let me know if I am misunderstanding something

Assume \(2^k>2k\) for some \(k\). //This is our hypothesis (correct statement)

Multiply both sides by \(2\)

\(2^k*2>2k*2\)

This gives

\(2^{k+1}>2k*2=4k=2k+2k>2k+2=2(k+1)\)
//A new equality is derived for 2^n+1 which only works if our hypothesis was indeed correct

So we have shown \(2^k>2k\implies 2^{k+1}>2(k+1)\)
// This Statement is only true if \(2^k>2k\) is true. How is that going to be proved?

So by induction \(2^n>2n\) for all \(n\ge 3\)

Answer 66

Btw in many other site 2^k>2k ==> 2^(k+1)>2(k+1) was a elementary step which was reached by showing that if a statement was correct for k than it will be correct for k+1. There were many steps after that

Answer 67

Here I'll take a more concrete approach.

\[2^3 > 2*3\]\[2^4 > 2*4\]\[2^5>2*5\]\[\cdots\]

So we can sorta see that there are infinitely many true statements we're looking to show true and we can evaluate the first one exactly as saying \(8 > 6\).

Now we have two options, we could choose to evaluate \(2^4>2*4\) and say "ahh it's true" upon seeing \(16 > 8\) but this strategy leaves us with having to prove every single statement this way one by one.

The other way to prove the second statement is to start here:
\[2^3 >2*3\]
Now we multiply both sides by 2 and a little algebra rearrangement.
\[2^4>2(2*3) > 2*4\]

This strategy can be used more generally though to step up from \(2^4>2*4\) up to proving \(2^5>2*5\) as well; which is what you've done with all the algebra k and k+1 stuff. I don't know if this quite clears up the concept of what you're doing or not.

Answer 68

And inductively 2^3>2*3 can also be proven correct if we had multiplied 2^2>2*2 by 2. Right?

Answer 69

no because \(2^2 > 2*2\) is false, \(2^2 = 2*2\) :D

Answer 70

Okay one last thing, how are we sure that the equality remains true for n+1?

Answer 71

Which equality?

Answer 72

2^n >2n

Answer 73

Well it's true when \(n=3\) right? Then that means it's true for \(n=4\) agree or disagree?

Answer 74

Disagree because what is the proof behind this?

Answer 75

This question is lagging my computer can you start a new question fresh xD

Answer 76

Btw No need because I think I got it. 2^n+1 implies that it is not only greater than 2n but it also greater when 2 is added on right hand.

Answer 77

I'm not sure, too vague for me to agree/disagree with that

Answer 78

Overview is this:

f(3) is true

when f(n) is true implies f(n+1) is true.

Then it autmatically steps up to all statements starting from f(3) implies f(4) is true. And now that you know f(4) is true it imples f(5) is true, and it repeats up and up

Answer 79

Overview is this:

f(3) is true

when f(n) is true implies f(n+1) is true. //This assumption is what confusing me. Why is the assumption correct?

Then it autmatically steps up to all statements starting from f(3) implies f(4) is true. And now that you know f(4) is true it imples f(5) is true, and it repeats up and up

Answer 80

start a new question

Answer 81

@FaiqRaees


I will explain induction to you.

Imagine you have some dominoes and you set them up.

Now imagine I can show you that no matter what, if you knock down a domino behind some other domino then the later domino will fall.

But this is not enough to insure that all dominoes fall, we must first assert that the very first one falls.

This is just like induction. You want to show that if some statement is true for SOME n, then it is true for the next one.

So in your case, we assume \(2^n>2n\) for SOME n. Note that this is NOT assuming the conclusion because we are trying to show it is true for ALL \(n\) and here we are just assuming it is true for some \(n\) and of course this is true because it is easy to show for \(n=3\).

So we may assume it is true for some \(n\). (again we are not assuming it is true for all \(n\) )

So we have that there exists SOME \(n\) such that \(2^n>2n\). We now want to show that this assumption about SOME particular \(n\) will extend to the next \(n\), in other words we want to show \(2^n>2n \implies 2^{n+1}>2(n+1)\).

So

Assume \(2^n>2n\) for some \(n\), then we have

\(2^n>2n\implies 2^n*2>2n*2\) this is obviously true.

This leads to \(2^{n+1}>2n*2=4n=2n+2n>2n+2=2(n+1)\)

Thus \(2^n>2n\) for all \(n\ge 3\) as required.

This might all be easier to understand, if you use \(k\) instead of \(n\) and many people do use \(k\) for this reason. i.e. assume it is true for some \(k\in \mathbb{N}\) and then show that this implies it is true for \(k+1\).