math help!!!!

[Tchen811]

Ok, I am taking this discrete math class and it's kicking my a$$. So anyone who can help is great...ok here is the problem:

Use induction to prove that postage of 24 cents or more can be achieved by using only 5 cent and 7 cent stamps.

Where do I start?

 

[cchen]

Alright, so how would you approach the problem? (The first step of induction)

 

[Tchen811]

do i start with a basis?

 

[cchen]

Right, prove for a base case...
just follow the steps for induction, shouldn't be very complicated

 

[Tchen811]

this is where I get stuck....what should the base case be? Is it like assume n=24? since the question asks for 24 or more?

 

[Yomicron]

Originally posted by: Tchen811
this is where I get stuck....what should the base case be? Is it like assume n=24? since the question asks for 24 or more?

yes the base case would be the lowest possible amount, in this case, 24.

 

[Krakerjak]

hmmm, dont take discrete math but maybe
P() = 24 + n
for all reals greater that 24

and
5x + 7y = 24 + n

 

[TuxDave]

first show that you can make 24 cents with 5 and 7 cent stamps. That's your base case. Then you gotta prove that given that you can do it for n cents, you can do it with n+1 stamps. This one isn't very mathematical. Here's a hint... 4*5 = 20... 3*7 = 21.. oooooh....

 

[lukatmyshu]

Originally posted by: TuxDave
first show that you can make 24 cents with 5 and 7 cent stamps. That's your base case. Then you gotta prove that given that you can do it for n cents, you can do it with n+1 stamps. This one isn't very mathematical. Here's a hint... 4*5 = 20... 3*7 = 21.. oooooh....

You can't just use normal induction ... I'm fairly sure you have to use strong induction (in case you're unaware instead of assuming that
P(N) is true you assume that P(1....N) is true ... so that showing that you can derive P(N+1) from P(N) you have to derive P(N+1) from ANY P(a) s.t. a is less than or equal to N. makes your life a lot easier

 

[TuxDave]

Originally posted by: lukatmyshu

Originally posted by: TuxDave
first show that you can make 24 cents with 5 and 7 cent stamps. That's your base case. Then you gotta prove that given that you can do it for n cents, you can do it with n+1 stamps. This one isn't very mathematical. Here's a hint... 4*5 = 20... 3*7 = 21.. oooooh....

You can't just use normal induction ... I'm fairly sure you have to use strong induction (in case you're unaware instead of assuming that
P(N) is true you assume that P(1....N) is true ... so that showing that you can derive P(N+1) from P(N) you have to derive P(N+1) from ANY P(a) s.t. a is less than or equal to N. makes your life a lot easier

Actually... you can use normal induction. He's just wants a proof for 24 cents and greater so I'm ok if start at P(24). To prove that I'm not just pulling this out of my arse, here's the full proof.

Initial Condition:
24 Cents can be done with 2 5 cent stamps and 2 7 cent stamps. (2*5+2*7=24).... done

Induction: (for n >=24 as the proof requests)
Assuming you can do it with n. We wish to see if we can do it for n+1. If we have at least 2 7 cent stamps, we can remove 2 7 cent stamps and replace it with 3 5 cent stamps. Otherwise we can remove 4 5 cent stamps and put in 3 7 cent stamps.

Now gimme a sec for the 2nd part of the proof.

 

[TuxDave]

We see that we can do that strategy for the first move. I guess this is the utter crap proof that we can do the strategy, but it's 3am, like I care.

x = # 5 cent stamps
y = # 7 cent stamps

Step 1: x=2, y=2
Step 2: x=5, y=0
Step 3: x=1, y=3
Step 4: x=4, y=1
Step 5: x=0, y=4
Step 6: x=3, y=2 ... STOP

In step 6, we can just put that extra 5 cent stamp aside and we end up with x=2, y=2 again, so we can therefore repeat the 6 step cycle all over again. Haha.. laaame proof, can't think of anything else. This is the way I see it, perhaps there is a strong induction proof that I don't see.