Question

How would i show 2^n >n^2 by induction?

Answer 1

this doesn't look correct. take the case of n=2.

Answer 2

but its true after n=5

Answer 3

so what does the question state exactly?

Answer 4

Exactly: 2^n >n^2 if n is element of N and n is large enough

Answer 5

ok, so you can show its true for n=5.
then assume its true for n=k \((k\ge5)\):\[2^k>k^2\]and finally prove its also true for n=k+1

Answer 6

yes, im stuck on proving that n=k+1

Answer 7

ok, so for n=k+1, we get:\[2^{k+1}=2\times2^k\]and we assumed:\[2^k\gt k^2\]therefore:\[2^{k+1}=2\times2^k\gt2\times k^2\]

Answer 8

so you just need to prove that:\[2\times k^2\gt(k+1)^2\]for \(k\ge5\)

Answer 9

actually you just need to prove:\[2\times k^2\ge(k+1)^2\]

Answer 10

for \(k\ge5\)

Answer 11

if you expand \((k+1)^2\) then this reduces to proving:\[k^2\ge2k+1\]for \(k\ge5\)

Answer 12

In this case, would show that LHS=RHS or LHS>RHS?

Answer 13

yes

Answer 14

try finding what value of k makes this true:\[k^2-2k-1\ge0\]

Answer 15

i mean do i show that LHS=RHS or LHS>RHS? do i choose eithe?

Answer 16

you need to show BOTH

Answer 17

how did get \[k ^{2} \ge2k +1?\]

Answer 18

\[k^2-2k-1\ge0\]implies:\[(k-1)^2-2\ge0\]\[(k-1)^2\ge2\]therefore:\[k-1\ge\sqrt{2}\]therefore:\[k\ge1+\sqrt{2}\]

Answer 19

we has to prove that:\[2\times k^2\ge(k+1)^2\]therefore:\[k^2+k^2\ge k^2+2k+1\]one of the \(k^2\) terms cancels out

Answer 20

I am assuming \[RHS=k^2 +2k+1\]

Answer 21

and from that i use the assumption

Answer 22

?

Answer 23

When i prove by induction, i prove the LHS and RHS seperately...

Answer 24

let me try and summarise the steps for you...

Answer 25

we first showed that:\[2^5>5^2\]which shows that:\[2^n\gt n^2\]for \(n=5\) - agreed?

Answer 26

Like, i want to know how from \[RHS=k^2+2k+1 \] would i incorporate the assumption

Answer 27

yes i agree

Answer 28

ok, so next step was to /assume/ this relation is true for some \(n=k\) where \(k\ge5\), so we get:\[2^k\gt k^2\]agreed?

Answer 29

yes i agree

Answer 30

ok, so next step was to then prove, assuming its true for \(n=k\), that it's also true for \(n=k+1\) where \(k\ge5\).
so all we need to prove is:\[2^{k+1}\gt (k+1)^2\]for \(k\ge5\) - agreed?

Answer 31

yes

Answer 32

ok, so if we look at just the term \(2^{k+1}\) we see that this can be written as:\[2^{k+1}=2\times2^k\]but, we have already assumed that:\[2^k\gt k^2\]therefore we can assert that:\[2^{k+1}=2\times2^k\gt2\times k^2\]agreed?

Answer 33

so you are saying that \[RHS=2^k \times 2 and thus RHS>2timesk^2\]

Answer 34

you know that:\[2^{k+1}=2\times2^k\]correct?

Answer 35

so you just replaced 2^k with k^2 and the = must now be > after substituting?

Answer 36

yes

Answer 37

yes, i agree

Answer 38

ok, so the last step we got to was that we have so far proved that:\[2^{k+1}\gt2\times k^2\]

Answer 39

now, what we /need/ to prove is that:\[2^{k+1}\gt(k+1)^2\]correct?

Answer 40

yes

Answer 41

ok, so if we can prove that:\[2\times k^2\ge(k+1)^2\]then we have proved that:\[2^{k+1}\gt(k+1)^2\]agreed?

Answer 42

yes

Answer 43

good - so lets see what values of k satisfy the equation:\[2\times k^2\ge(k+1)^2\]

Answer 44

we get:\[k^2+k^2\ge(k+1)^2\]\[\cancel{k^2}+k^2\ge \cancel{k^2}+2k+1\]\[k^2\ge 2k+1\]\[k^2-2k-1\ge0\]\[(k-1)^2-2\ge0\]\[(k-1)^2\ge2\]\[k-1\ge\sqrt{2}\]\[k\ge1+\sqrt{2}\]

Answer 45

but we wanted this to be true for \(k\ge5\) so we have now proved what we wanted.

Answer 46

\[2k <2^{k}\]

if k<0 conjecture is true as LHS <0 andRHS>0 For k=1 , 2*1-2^1 is true

assume true for k=n

\[2n<^{2^{n}}\]

then
\[2n \times2<2^{n}\times2\]
\[4n <2^{n+1}\]
\[2n+2n <2^{n+1}\]

so \[2n+2<2^{n+1}\] as \[2n >2 for n >1\]
i.e. \[2(k+1)<2^{k+1}\]

if conjecture is true fork=n then it is true for k=n+1

proved

Answer 47

you mean the fact that 5 is greater than 1+ sqrt(2) is proven?

Answer 48

yes

Answer 49

and that is all?

Answer 50

yes :)

Answer 51

yu guys made it very complicated :/

Answer 52

hang on, i agree with you now :) but what i mean is, have we shown that LHS=RHS?

Answer 53

@Tushara we were not trying to prove \(2k <2^{k}\)

Answer 54

oh oops sowwie

Answer 55

we have proved:\[2^n\gt n^2\]for \(n\ge5\)

Answer 56

ok sweet

Answer 57

@Tushara np - its good to have other people double checking your work - we can all make mistakes from time to time :)

Answer 58

like what i am doing: