Question

can anyone help me understand strong induction? Im having trouble with it.

Answer 1

i understand the definition that to prove P(n) is true for all positive integers n, where p(n) is a propositional function, we consider 2 steps:
Basis: we verify that it is true for when P(1)
Inductive step: we show that the conditional statement [P(1)andP(2)...andP(k)] implies P(k+1) is true for all positive integers k.

Answer 2

It seems you already have it down. I'm trying to find a good example for it, though... stand by :D

Answer 3

alright i just dont understand the steps i should go through. and when i follow the examples i dont feel like they actually prove anything

Answer 4

Can you understand how basic Mathematical Induction proves things, though?

Answer 5

yes i understand those completly. sometimes i get stuck on the algebra but i understand why they work and how to do them

Answer 6

Then Strong Induction is when assuming that it holds true for just the previous natural number isn't enough :)

Answer 7

Normal Induction goes
[1]Base Step: Show it holds for 1
[2]Inductive step: Show that IF it holds for k, it holds for k = 1.

Once you've done this, you've basically proven the thingymajig for ALL positive integers, because...
Because you showed it holds for 1
And you showed if it holds for k, it holds for k + 1
It holds for 1, then it holds for 2, then it holds for 3, etc...

Answer 8

ok so i have an example from my book. want me to type the question?

Answer 9

Now, for Strong Induction, it goes
[1]Base Step: Show it holds for 1
[2]Inductive Step: Show that IF it holds for all positive integers less than k, it holds for k

Once you've done this you've basically proven the thingymajig for ALL positive integers, because...
Because you showed it holds for 1
And you showed that if it holds for all positive integers less than k, it holds for k.
Let k be 2. It holds for 1, so it holds for all positive integers less than 2, therefore, it holds for 2.

THEN it holds for all positive integers less than 3, so it holds for 3....

THEN it holds for all positive integers less than 4, so it holds for 4...
etc :D

Answer 10

I'd love to see the question :)
No guarantees though

Answer 11

haha ok thank you. it says "suppose that a store offers gift certificates in denominations of $25 and $40. determine the possible total amounts you can form using these gift certificates. prove your answer using strong induction."

Answer 12

Ok, processing...

Answer 13

the previous question was easier because it used $2 and $5. we can use that insted if you would like lol. im closer to understand that one then this one.

Answer 14

still have no idea :D
But don't worry, I don't give up so easily .
I'm sure if we can solve one of these two, then the other is easily solvable :)

Answer 15

alright lol so here is what i think (kinda using the key) for the $2 and $5. well you can obviously make $2 and $4. so we need to prove it for n>=5

Answer 16

so the basis says that if n=5 then you can form 5 using a $5 and you can form $6 using 3 $2's

Answer 17

Right...

Answer 18

Assume the inductive hypothesis, that P(j) is true for all j with 5<=j<=k, where k is an arbitrary integer grater then or equal to 6. we want to show that P(k+1) is true, that is, that we can for k-1 dollars. add another 2dollar bill, and we have formed k+1 dollars.

Answer 19

Oh, okay. I have found a way to prove that you can form any amount bigger than 5, but not using strong induction, just normal induction...

Answer 20

so for strong induction we assume that the statement is true for some number j between our basis and what we want to prove right?

Answer 21

I still have no idea how to prove the $2 $5 thing by strong induction... o.O

Answer 22

ok i think im getting it. let me try rewording it tell me if it makes sense

Answer 23

so we need to prove that we can make anything >=$5 (because we can clearly make 2 and 4 dollars).

Answer 24

the basis says that 5 dollars can be made with a 5 dollar bill.

Answer 25

the inductive hypothesis sas that we can make $k where k is >=5

Answer 26

wait crap lol idk

Answer 27

here... ill just type out the question and the answer of a similar question we did in class. my book is clearly not very clear lol.

Answer 28

prove that you can form any amount >= 60 using only 4's and 7's using strong induction.
BASIS: when n=60, you use 15 4's to make 60.
INDUCTIVE STEP: Let k>= 60. suppose you can form 60,...,k.
case 1: k-3>=60; by inductive hypothesis, we can form k-3. then adding a 4 will give us k+1.
case 2: k=62; using 12 4's and 2 7's
case 3: k=61; using 10 4's and 3 7's
cas3 4: k=60; using 15 4's

Answer 29

Actually, to make it simpler (I think?) let's go until $9
Show that we can make all the amounts from 5 to 9, using 2's and 5's
5 = 5
6 = 3(2)
7 = 5 + 2
8 = 4(2)
9 = 5 + 2(2)

Now, suppose we have a number k > 9, such that it can be formed using 5's and 2's
Then
k = a(5) + b(2)
Where b is greater than or equal to 2.
Then k + 1
= a(5) + b(2) + 1
= a(5) + b(2) + 5 - 4
= (a+1)(5) + (b-2)(2)
And thus, k+1 can also be formed using 5's and 2's

Answer 30

ah ya ok that makes sense
thank you

Answer 31

:)