Question

what do we do mathematical induction?

Answer 1

who?

Answer 2

imagine dominoes, if they are set up right, and you knock over the first one, and it hits the second one, we know the rest will fall.

Answer 3

this is induction.

Answer 4

@MathsStar make sence at all?

Answer 5

mathical induction assumes that you can get from here to there if you do the same thing over and over and over again; if you can keep putting one foot in front of the other

Answer 6

imagine people walking in a line, if the first guy starts to move, and you look at some random place in the line and they are also moving, then they all must be moving....we know the first guy is moving, and since someone else is moving they must be moving, because if anyone stoped the entire line behind them would have to stop.

Answer 7

why do we do mathematical induction?

Answer 8

it beats trying to prove an infinite number of cases

Answer 9

to prove things
say we want to prove 2n+1 <2^n when n >=3

Answer 10

we can show it is true for n = 3
then we assume its true for some case(that case) and using that assumption we need to show its true for n+1, if we can do that its true for all n in N

Answer 11

note it works best with natural numbers buthere is a way to do it on the real line, but its very complicated.

Answer 12

also there are two types of induction on the naturals. We are explaining the "main" one, or induction one...

Answer 13

strong induction ... never did really see the differences

Answer 14

Yeah I had to use it once in nunmber theory because I could not do it with induction, but only once.

Answer 15

when there is an inequality that is whre i have a problem of solving the mathematical induction. eg \[4n <2^{n}\]

Answer 16

follow up in my statemen above. where n is greater or equal to 5 in my statemnt above

Answer 17

check if its n=5 works

if so, assume: 4k < 2^k

multiply both sides by 2: 8k < 2^(k+1)

now, is 4(k+1) < 8k ? of so .... we got ourselves a winner

Answer 18

amistre64 i dont understand why u multiply with 2

Answer 19

just a property of exponents, we want to get to a \(2^{k+1}\)
\[\Large a^b~a^c=a^{b+c}\]
\[2^k~2^1=2^{k+1}\]

Answer 20

the k+1 part is the induction

Answer 21

now, when is 4(k+1) < 8k ?

4k+4 < 8k

4 < 4k ; for all k > 1

Answer 22

in effect,
\[4k<2^k\]
\[4k<8k<2^{k+1}\]
\[4k<4(k+1)<8k<2^{k+1}~:~k>5\]

Answer 23

im just lost

Answer 24

do you agree that 2^x times 2 = 2^{k+1}?

Answer 25

keep in mind that we are looking to prove that: 4(k+1) < 2^{k+1}

Answer 26

not 2^x ... bad fingers ...

Answer 27

yes i agree

Answer 28

then we have our setup as:

4k < 2^k multiply each side by 2

8k < 2^{k+1}

we know know that 8k is less than 2^{k+1}; so we have something to compare with

Answer 29

if we can prove that: 4(k+1) is always less then 8k, we have made our case

Answer 30

why multiply by 2?

Answer 31

remember the restriction is n is greater or equal 5

Answer 32

4(k+1) < 8k ; dividing by 4 is fine as well

k+1 < 2k

1 < k ; so for all k greater than 1, 4(k+1) < 8k; which is less then 2^(k+1)

Answer 33

ive already shown a few time why multiplying by 2 gets us to be able to evaluate 2^(k+1)

you even agreed the 2^k times 2^1 equals 2^(k+1)

Answer 34

the k+1 is the "next" step .. if its true for some k, and we know its true for k=5, then we have to show that it is true for k+1 as well.

if so, then it is true for the values of k equal to: 5, 6, 7, 8, 9, 10, 11, 12, ...

Answer 35

since its true for 5, is it true for 5+1? yes
since its true for 6, is it true for 6+1? yes
since its true for 7, is it true for 7+1? yes
since its true for 8, is it true for 8+1? yes

how do we know? because it is true for k, and also true for k+1

Answer 36

the only way to show the it is true for k+1, we have to get 2^k adjusted, augmented, swapped out for .. 2^(k+1)

Answer 37

so, we know it is true for some k; k=5

4k < 2^k, is 4(k+1) < 2^(k+1) ?? lets see

2*4k < 2*2^k

8k < 2^(k+1) , why did i multiply by 2?

Answer 38

so we have proven that 8k is strictly less then 2^(k+1)

can we show that 4(k+1) is strictly less then 8k ? if soo then: 4(k+1) has to be stricly less than 2^(k+1) for all k

Answer 39

why multiply 2*4k on the hypothesis

Answer 40

well, we would like to have something to compare 4(k+1) with, and that is not going to be 4k

Answer 41

cz i get the RHS its 2^{k+1} which give 2^k.2

Answer 42

its always a good measure to do the same thing to BOTH side of the equality sign

Answer 43

all that we can prove by NOT multiplying 2 to the 4k is that: 4k < 4(k+1) this does not give us proof that 4(k+1) is less then 2^(k+1)

Answer 44

by showing that 8k < 2^(k+1) we can then assert that anything that is less than 8k must be less than 2^(k+1)

Answer 45

May i please type in the solution that i have for this problem from my textbook , i just wana shw you how they solved it. but i dont understand some steps in there

Answer 46

that would be fine

Answer 47

however with what u explained above i think i follow you

Answer 48

im wondering if your computer froze :/

Answer 49

Prove that \[4n <2^{n}. for all n \ge 5.\]
Let P(n) denotes the statement \[4n <2^{n}\]
P(5) ia the statment that \[4\times5<2^{5}, or 20<32, which is true\]
Assume that P(k) is true. Thus our hypothesis is \[4k < 2^{k}\]
we want to use this to show that P(k+1) is true, that is, \[4(k+1)<2^{k+1}\]
so we start with the left -hand side of the inequality and use the induction hypothesis to show that it is less than the right hand side. For \[k \ge5\]

\[4(k+1)=4k+4\]
\[<2^{k}+4\]
\[2^{k}+4k\]
\[2^{k}+2^{k}\]
\[=2\times2^{k}\]
\[=2^{k+1}\]
Thus P(k+1) follows from P(k), and this completes the induction step. Having step one and two , we can conclude that by the Principle of Mathematical Induction that P(n) is true for all natural numbers \[n \ge5.\]

Answer 50

i see that they went with adding 4 to each side to start with

4(k+1) < 2^k + 4

not real sure why the next line is +4k, then +2^k

Answer 51

step two and three its an less inequality . and i dont understand from \[<2^{k}+4 downdwards\]

Answer 52

i see

Answer 53

we know that 4 < 4k < 2^k

Answer 54

\[since~4<4k<2^k~:~recall~4k<2^k~by~hypothesis\]

Answer 55

\[4(k+1)<2^k+4\]
\[4(k+1)<2^k+4<2^k+4k\]
\[4(k+1)<...<2^k+2^k\]
\[4(k+1)<...<2*2^k\]

Answer 56

i liked my idea better :) same results tho.

dont get hooked on one particular solution over another tho.

Answer 57

You are perfectly right . i should not get hooked on one particular solution . i think i will have to use you method. . but then in ur method . i dont see you writing step by step like i did in words above.

Answer 58

like telling your P(n) and (5 or any) and P(k) and P(k+)

Answer 59

mean P(k+1)

Answer 60

...mines more spread out :)

\[4k<2^k~:~assumed ~true\]
\[2*4k<2*2^k\]
\[8k<2^{k+1}\]
\[4(k+1)<8k\]
\[k+1<2k\]
\[1<k\]
\[4(k+1)<8k<2^{k+1}\]
\[4(k+1)<2^{k+1}~:~k>=5\]

Answer 61

yeah, i assume you are able to fill in the details of P(n) to P(k) and such

Answer 62

i havent had to take a proof writing intensive class yet ... they tell me its coming tho

Answer 63

yes i am...you are a ToP Dog. now how do i get myself undertanding this i mean honestly underdandind not for just an exam, but even tommrw if i wake up i can be able to do it. particularly i like your way

Answer 64

its all about trying to see the start and finish, and working a strategy to get from one to the other.

prove it is true for a particlar n
assume it is true for some n=k
jot down what the end result is to focus on
use what you have at the start to work logically to the end

there are still alot of induction problems i have troubles with

Answer 65

you generally do not have to prove the basic algebra that comprises the inbetween stuff; but if you think it clarifies some step, you might want to expound upon it ...

Answer 66

Thanks for that. So tell me what kind of induction u have problems with and why....cz u have a good strategy of dealing with them

Answer 67

because my assumptions is that if can manage this basics you can manage any.. isnt that so?

Answer 68

alot of the time i work it backwards, or so ive been told. the basics are nice yes, but the real learning is just in doing and doing and doing as many as you can come across; look at other peoples setups and reason them out in your mind.

Answer 69

ill assume the k+1 is true and tend to work it to the kth step ... my teachers just shake their heads

Answer 70

that of course is a good way to see how you should step it forwards, but i have a propensity to forget to reverse it lol

Answer 71

lol..........funny but true it did work. Therefore by the Principle of Mathematical induction P(n) is true for every efforts u applied to sustain ur knowledge.

Answer 72

i must be off to the house ;) you have fun and good luck

Answer 73

wait a minute. are u a student?

Answer 74

?

Answer 75

im in college at the moment yes, but feel that i am too old to be considered a "student" perse

Answer 76

my teachers tend to be younger than me :)

Answer 77

ciao

Answer 78

how old are you and what are you studying and where. which country?