Question

prove that for all n>0, n!>=2^(n-1) using induction

Answer 1

basis step using n=1 is true

Answer 2

plugging in n+1

Answer 3

\[(n+1)n!\ge2^{n-1}(2)\]

Answer 4

\[n!\ge2^{n-1}(\frac{ 2 }{ n+1 })\]

Answer 5

we know n>0, n+1>1, n+1>=2 (because n cannot be non-integer?)

Answer 6

here's where I get stuck

Answer 7

you assume the statement true for n
so, you have n! > = 2^(n-1)
now you need to prove
(n+1)! > = 2^n [replacing n by n+1]
right ?

(n+1)n! > = 2^(n-1) (n+1)
(n+1)! > = 2^n [(n+1)/2]
since , n > 0 (n+1) /2 > 0
so,(n+1)! > = 2^n

Answer 8

ok, in the second line, is n+1 in the exponent on RHS

Answer 9

no... n+1 was multiplied on both sides...its not in exponents.

Answer 10

don't we replace all instances of n with n+1?

Answer 11

doing it on paper the way you suggested, i think i see what you mean, multiplying by n+1 on both sides is the way of proving for n+1 in inductive step

Answer 12

i hope u understand my solution, let me know if u need help

Answer 13

tushara, do you agree with the other answer in this question?

Answer 14

the only thing m not sure about with the other solution that hartn did is that,,,, (n+1) was multiplied with the power.... i thot u cant do that, u can multiply it with the whole eqn on the rhs side but u cant multiply it just to the power

Answer 15

in my solution i wrote k+1=k=n.... scratch dat, it shud be....k+1=n+1 and from there it follows right

Answer 16

are we allowed to draw the conclusion that the RHS changes similarly to the LHS, where RHS must be 2^(k+1-1)

Answer 17

yes , ive seen other proofs which were done dis way

Answer 18

how do you end up with k - k - 1 for k!

Answer 19

is it because there are k items?

Answer 20

because wen u do the factorial... u end up multiplying my 1 in the end right? so k-(k-1) will give 1..... so say k was 3.... 3-(3-1)=1 so the last number u multiply by is 1

Answer 21

its important to remember how to expand a factorial... its always: n! = n*(n-1)*(n-2)*...........n-(n-1)

Answer 22

gotcha

Answer 23

is there a technical term for proving in the manner you did, "take notice"

Answer 24

nice... HI5!

Answer 25

wat is the technical term?

Answer 26

i'm asking you...my professor may request my source

Answer 27

oh uhm sorry, i read ur reply wrong...... uhm no... i cant think of putting that in a more proffesional way.... u shud ask ur friends how dey went about it

Answer 28

will do, i'll call it something like "rule of equalities"

Answer 29

cool

Answer 30

thanks again

Answer 31

\( n! > = 2^{(n-1)}\\(n+1)n! > = 2^{(n-1)} (n+1) \\
(n+1)! > = 2^n [(n+1)/2]\)
never multiplied anything with exponent...

Answer 32

your proof seems more conventional

Answer 33

can you tell me how you came to the conclusion
since , n > 0 (n+1) /2 > 0
so,(n+1)! > = 2^n

Answer 34

n > 0 (n+1) /2 > 0 is pretty logical. if n is positive no., n/2 +1/2 will also be positive .

Answer 35

yes, got the logical part

Answer 36

(n+1)!>=2^n[(n+1)/2]
its like x>= ab
if b is positive and >=1, then x will be >= a also.
so, we need (n+1)/2 > =1
since n is atleast =1, (n+1) is atleast 2 and (n+1)/2 is atleast 1
so, (n+1)/2 >=1

Answer 37

how does (n+1)! > = 2^n relate to our inductive assumption?

Answer 38

3 steps for induction.
1) prove it for n=1
2) assume it for n=n
3) using 2) prove it for n=n+1
...some people use new variable 'k' to avoid confusion....

Answer 39

oh, i must be blind, 2^n === 2^(n+1-1)

Answer 40

it's proved then for n+1

Answer 41

yes.

Answer 42

one more qustion, we know that (n+1)/2>0, but what if it is a very large number? could htat make the RHS bigger than LHS?

Answer 43

(n+1)! >= 2^n (1,000,000,000)
for example?

Answer 44

RHS =0
any large +ve no. +1/2 = +ve no > 0
so RHS can never be > LHS

Answer 45

ok, thanks

Answer 46

or was your doubt something else ?

Answer 47

no, it is reasonable to think that LHS will grow larger than RHS, if the n becomes larger