Question

I need some help with inductions pleaseee

Answer 1

Do you have a more specific question? (example?)

Answer 2

yeah,
\[2^{n-1} \le n!\] @reemii

Answer 3

Can you recall the basic steps of the proof? how the parts of the proof are called…

Answer 4

I got down to the n=k+1 part and got
\[2^{k} \le (k+1)! \]
and my assumption is just
\[2^{k-1} \le k!\]

Answer 5

now i'm kinda stuck

Answer 6

what is n?

Answer 7

The answer is: "use your assumption now". Your assumption and "n=k+1" reads:
given that \(2^{k-1} \le k!\), I must show that \(2^k \le (k+1)!\).

So, do you see why that must be true? (Hint: \(2^k = 2^{k-1+1}\)).

Answer 8

is n just a positive integer
or is a subset of the positive integers ?

it looks like it is the set of positive integers

Answer 9

All positive integers @freckles and yes, but i don't know where to go from there @reemii

Answer 10

use law of exponents

Answer 11

\[2^k=2^{k-1}2\]
now use inductive hyp

Answer 12

am i working with my assumption now?

Answer 13

yes

Answer 14

so, it would be
by assumption
\[2^{k-1}\le k!\]
\[2^{k-1+1}\le k! \] ???

Answer 15

you dropped the 2

Answer 16

\[2^{k-1+1}=\color{red}{2^{k-1}}2 \color{red}{\le ...} 2\]
what should go in place of those dots ....

Answer 17

you also have \(k! = (k-1)!\times k\).
Observe the inequality \(2^k\le k!\) using the two decompositions: \(2^k=2^{k-1}2\) and \(k!=k\times(k-1)!\).
Can you conclude?

Answer 18

Where are you guys getting the 2 after the 2^(k-1)??

Answer 19

ohh nvm gotcha

Answer 20

we are trying to show
\[2^k \le (k+1)! \\ \text{ we are starting with the \left hand side } \\ 2^{k}=2^{k+1-1}=2^{k-1+1}=2^{k-1}2 \\ \text{ we wrote } 2^k \text{ as } 2^{k-1} 2 \\ \text{ \because we know something about } 2^{k-1}\]

Answer 21

Okay i see. And for the RHS it's 2k! so when i write tht out (which i would do right?) it would be (2k)x(2k-1)! or would it just be 2(k)x(k-1)! ?

Answer 22

oh I was having trouble reading what you wrote yeah you have
\[2^k=2^{k-1}2 \le k! \cdot 2 \text{ by your inductive hyp }\]

Answer 23

and then I think @reemii gave you a hint above somewhere on how to continue

Answer 24

About the (k-1)! ?

Answer 25

What do i do with tht extra 2 on the right side though?

Answer 26

You have all elements to finish. "If \(a≤b\) and \(c≤d\) and the numbers are positive, what about \(ac\) vs \(bd\)?

Answer 27

That makes sense but what are my 2 inequalities that i'm comparing??

Answer 28

remember what you are trying to show
and I like to repeat this because it is important on figuring out what to do next
\[2^k \le (k+1)! \text{ is what we want to show } \\ 2^k \le k! \cdot 2 \text{ is what we have so far }\]

Answer 29

earlier @reemii said something about k!=k*(k-1)!
what does (k+1)! equal if I wanted to write it as a product of two things

Answer 30

just like he did with the k!

Answer 31

(k+1)(k)(k-1)!

Answer 32

that is true
but a product of two things
like (k+1)!=(k+1)*k!

Answer 33

notice we already have k! on our right hand side

Answer 34

But i thought i was working on the assumption and all there is is a 2k!

Answer 35

what do we know about comparing 2 and k+1 though

Answer 36

remember k is a positive integer

Answer 37

so what symbol can I use to compare 2 and k+1

Answer 38

\[\le \]

Answer 39

right on

Answer 40

Where are you getting the 2 and k+1?

Answer 41

so you would say the following is true right
\[2^k \le k! \cdot 2 \le k! \cdot (k+1)\]

Answer 42

I'm trying to remember what I want to show
and where I'm at to figure out what to do

Answer 43

for example we wanted to show
\[2^k \le (k+1)! \\ \text{ or you can write this as } 2^k \le k! \cdot (k+1)\]

Answer 44

Ohh i see so you can go up from k? So (k+1)(k+2)! etc.. i thought you could only go down?

Answer 45

no no

Answer 46

Oh thats the other one

Answer 47

My bad xD

Answer 48

(k+1)! = k! * (k+1)
not (k+1)*(k+2)!

Answer 49

sort of "visual" presentation of what all happened here:
\[
\begin{align}
2 &\le k\\
2^{k-1}&\le k!\\
& \downarrow\\
2^{k-1}2&\le k(k-1)!
\end{align}
\]

Answer 50

ugh. first line should be \(2\le k+1\) and second \(2^{k-1}\le k!\).

Answer 51

So (k+1)!=(k+1)*(k)! (and if i were to hypothetically continue the next would be k-1 correct?)

Answer 52

yes

Answer 53

(k+1)k(k-1)! etc.

Answer 54

Okay so as of right now i have my "by assumption" part saying
\[2^{k}\le 2k!\]

Answer 55

and you already said 2<=k+1

Answer 56

you will need that inequality as well

Answer 57

wait when did i say that part?

Answer 58

above when I asked you the following:
"so what symbol can I use to compare 2 and k+1"

Answer 59

Oh that's the one we just came up with right?

Answer 60

So it's not like its stated anywhere?

Answer 61

it is not clearly stated anywhere
it is derived from the information given

Answer 62

we are using that because we want to show what we have is <=(k+1)!
aka <=k! * (k+1)

Answer 63

Okay, so then..
\[2^{k}\le 2k! \le (k+1)k!\]
is that right..?

Answer 64

yes you used there that 2<=k+1
good job

Answer 65

Thanks! Then from there what do i do?

Answer 66

(k+1)!=(k+1)*k!

Answer 67

2k≤2k!≤(k+1)!

Answer 68

\[2^{k}=2^{k-1+1}=2^{k-1}2 \le k! \cdot 2 \le k! \cdot (k+1)=(k+1)!\]
you can finally write the final sentence of your proof

Answer 69

therefore this proves blah blah for all positive integer n

Answer 70

you might not want to say blah blah

Answer 71

Lol xD THANK YOU SO MUCH!!!! :)

Answer 72

It definitely clears things up :D

Answer 73

yeah i do admit that was probably one of the last things I grasped when doing induction proofs

you just have to have a goal and make up things that ARE TRUE to get there

Answer 74

Thanks!! Hopefully i can make things up that work out on my quiz :/

Answer 75

remember it has to be true things :p

Answer 76

Yes :P

Answer 77

Thanks again!!!

Answer 78

np