Question

@zzr0ck3r n^2 ≤ n!, for any integer larger than 3. Prove by induction

Answer 1

I have a clue already of what to do.

Answer 2

Basis step, n = 4.

Answer 3

(16) ≤ 24

Answer 4

Inductive step is *n+1)^2 ≤ (n+1)!

Answer 5

(n+1)^2 ≤ (n+1)!

Answer 6

but then I get confused on how to move from there... I want to solve or arrange the RHS. to (n+1) n!

Answer 7

we dont need the 4th line. I started writing before I knew how to do it...

Answer 8

Could you please explain the last two lines for me , sorry

Answer 9

mostly the last line really

Answer 10

no take 6! this is 6*5*4*3*2*1 = 6*5!

Answer 11

make sense?

Answer 12

oh the factorial equivalent is clean. it is mostly the last part. the conclusion

Answer 13

for (n+1)! = (n+1)n!

Answer 14

ok

Answer 15

And (n+1)∗n!≥(n+1)2n≥2∗2n=2n+1 for all n≥4

Answer 16

so \((n+1)! = (n+1)n! \) and by assumption \(n^2 \le n!\) so \((n+1)! \ge(n+1)2^n \) right?

Answer 17

what is the last part

Answer 18

2n

Answer 19

sorry n^2

Answer 20

let me write this better

Answer 21

thanks

Answer 22

\(\large n^2 \le n!\) for \(n\ge 4\)
Ok we know its true for \(n = 4\)
So assume \(n^2 \le n!\)
Now we want to show that \((n+1)^2\le(n+1)!\)
Well \((n+1)^2=(n+1)(n+1)\) and \((n+1)!=(n+1)n!\). We know by assumption,
\(n^2 \le n!\)
So \((n+1)!=(n+1)n!\ge(n+1)n^2\ge(n+1)(n+1)=(n+1)^2\)

Answer 23

you might want to show, by induction, \(n^2 \ge n+1\) for \(n\ge 2\).

Answer 24

ok

Answer 25

this making more sense?

Answer 26

yeah a subproof is required

Answer 27

if your teacher is nice enough, you may simply use the proof duh!. Some like it, some dont... use at your own discretion

Answer 28

what they seem to do is derive inequalities

Answer 29

to a point where you have n^2 - n - 1 >= 0

Answer 30

sure, but this is just to get the hang of induction. It is a very powerful tool in all area of mathematics

Answer 31

and find the zeros and proof they are less than 4. I am just sure how we are supposed to come up with these things in our own

Answer 32

so then assume it will be an inductive proof for n >= 4, and some sort of contradiction im sure then is used.

Answer 33

just a guess:)

Answer 34

my class is online.. it has been very hard. I am doing it all on my own.

Answer 35

all that we get from our teacher is PDFs with notes.. that is it...

Answer 36

what class is it?

Answer 37

Discrete Mathematics 1 . CompSci major

Answer 38

I am very good at Math ... expect for proofs. I am very nervous I am going to get a B or C

Answer 39

just keep doing it.

Answer 40

this is where the math starts:)

Answer 41

you started with n^2 <= n!

multiply (n+1) both sides :
n^2(n+1) <= n!(n+1)
n^2(n+1) <= (n+1)!

you will feel stuck at this point i guess

Answer 42

you need to think of ways to get (n+1)^2 on left hand side

Answer 43

With induction, there is about 5 different "tricks" used, you will get used to them with a few more hours of practice. then they will all seem the same, and sort of fun. Just like trig identities.

Answer 44

Thats why you saw all the guys rush in here for the induction proofs, because they are fun:)

Answer 45

Lord Ganesha remove the obstacles in my way to an A!

Answer 46

one hint that may come in handy, is that summation notation many times makes induction proofs easy. you have not had one where we could have taken advantage of it, but im sure you will.

Answer 47

A! = A*(A-1)! = A(A-1)(a-2)! = .........

Answer 48

had to do it.

Answer 49

it has been so helpful ! I hope I do well

Answer 50

just keep at it.....dont go to sleep unless you understand it:)

Answer 51

I am seeing double lol and there is 2 more. I am not sure I can take it. lol my boyfriend is gonna dump me at this rate lol

Answer 52

All I do is work for his class.

Answer 53

I have not had any fun in 5 years.....get used to it and know that your life will rule when you are done.

Answer 54

There is this one @zzr0ck3r and @ganeshie8

Answer 55

Seems simple but I don't get it two well with the subsets.

Answer 56

ahh discrete...

Answer 57

subsets are just some of the stuff (or all, or none) of the stuff in the set.

Answer 58

@ganeshie8 you want this one? I want taco bell. If not ill do it.

Answer 59

on this proof i think they want to prove one has twice the number of the other ...I have intuition of what is being done , but I cannot support it mathematically

Answer 60

no take the set \(\{1,2,3,4\}\) they are saying there are 2^4 = 16 sub sets of this set
lets list them all \(\{\emptyset,\{1\},\{2\}, \{3\}, \{4\}, \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\},\{2,4\},\{3,4\}, \{1,2,3\},\\ \{1,3,4\},\{2,3,4\}, \{1,2,3,4\}\}\)

Answer 61

sorry that takes allot in latex///

Answer 62

I think I am missing one...what is it?

Answer 63

oh wow! thanks you went out of the way to get teh subsets

Answer 64

its missing one, but I cant see it...

Answer 65

dont worry lol

Answer 66

ill show you the proof when I get back, give me 20 minutes....

Answer 67

lol i may be dead by then

Answer 68

you want this using induction ?

Answer 69

yes, please

Answer 70

I need to be able to understand it well to explain it

Answer 71

basis step : n = 0

Answer 72

which is the empty set right?

Answer 73

\(\large S = \emptyset \implies |S| = 0 = n\)
\(\large \implies P(S) = \{\emptyset\} \)
\(\large \implies |P(S)| =1 = 2^0 \)

establishes the basis

Answer 74

got it! We are working with the cardinality!

Answer 75

exactly ! and our proof also has a name : cardinality of power set

Answer 76

How awesome ! I wish I had met you and zzrock hours ago :(

Answer 77

I think we are going to prove that 2^(n+1) is double the subsets that 2^n

Answer 78

thats it !

Answer 79

because 2^(n+1) = 2*2^n

Answer 80

I just don't know how to say in the terms the teachers wants lol I can write in in english like that

Answer 81

I think what happens is that for 2^(n+1) we get an extra elements.... prior to that element being added... we have the exact same sets as 2^n.. like a collection.. or a book previous edition.

Answer 82

so we happens is that with 2^(n+1), we add a new elements., creates a new edition.. and that element pairs with EVERY single previously existing subset to create a new unique subset in 2^(n+1)

Answer 83

your logic is perfectly correct. An induction proof has 3 steps :
1) show that the statement is true for `n=1`
2) assume the statement is true for some `n = k`
3) show that the statement will be true for `n=k+1`, whenever it is true for `n=k`.

just split your reasoning into 3 paragraphs and put it in above format :)

Answer 84

That is what I try to do , but I get stuck in the inductive step.

Answer 85

I am not sure if sentences are ok, or if I always need symbols.

Answer 86

check proof3 :
https://proofwiki.org/wiki/Cardinality_of_Power_Set

Answer 87

O_O lol I suck at theory

Answer 88

it feels so strange to me :(

Answer 89

haha no, that proof is using the exact same steps described by you earlier in induction step...

Answer 90

but with the weird symbolism I am not too good at interpreting

Answer 91

btw is your username related to Lord Ganesha?

Answer 92

Induction hypothesis :
assume \(\large |S| = k \implies |P(S)| = 2^k\)

and we need to show that \(\large |S| = k+1 \implies |P(S) = 2^{k+1}\)

Answer 93

S = set
P(S) = `power set` of set S

Answer 94

What is a power set sorry?

Answer 95

lol yes and your obstacles are removed a few moments ago :P