Proof by mathematical induction

[agnes1999]

I'm stuck on this problem
Prove any postage of 24 or more can be constructed using 5 and 7 cent stamps.

So far this is what I've had
24= 2x5 + 2 x7
25= 5x5
26= 1x5 + 3x7
27= 4x5 + 1x7

Basis n= 24 = 2x5 + 2 x7

How do I continue to the inductive step and the proof?

 

[Steven G]

Why use induction?
Note that 3*7 - 4*5 = 1. That is you can always add 1 to any linear combination of 7a + 5b. I understand that you only want a and b to be positive. I suspect that if the sum is is 24 or more that will not be a problem! (Thanks Dr P--I remembered to look for 1!)

 

[Dr.Peterson]

I'm stuck on this problem
Prove any postage of 24 or more can be constructed using 5 and 7 cent stamps.

So far this is what I've had
24= 2x5 + 2 x7
25= 5x5
26= 1x5 + 3x7
27= 4x5 + 1x7

Basis n= 24 = 2x5 + 2 x7

How do I continue to the inductive step and the proof?

Given that you are supposed to use induction, can you use strong induction?

Do you see that from 24 you can easily get 29, and from 25 you can get 30, and so on?

Or you might be able to use Jomo's idea with induction; another fact is that 3*5-2*7 = 1.

 

[agnes1999]

Given that you are supposed to use induction, can you use strong induction?

Do you see that from 24 you can easily get 29, and from 25 you can get 30, and so on?

Or you might be able to use Jomo's idea with induction; another fact is that 3*5-2*7 = 1.

I've never used strong induction. Just a mere understanding of how it should work. I've looked at a few examples and it doesn't get any easier.

 

[Steven G]

Please show us something. If you want to use induction then at lease show us the base case(s). Then try to state the induction hypothesis.
Seriously, no one here will do the work for you. We do not want you to go elsewhere as we really do want to help you. We believe that you doing the proof is in your best interest.

What do you think the difference is between weak and strong induction?

 

[Dr.Peterson]

I've never used strong induction. Just a mere understanding of how it should work. I've looked at a few examples and it doesn't get any easier.

So maybe you aren't expected to use it.

Are there any hints you were given, or any example problems that might be relevant? I need to see something that you do know, or have tried, in order to have a place to start. In addition to the basics of induction, what do you know of number theory and related concepts that might be used here? If I were helping you in person, I would be looking through your text and looking for ideas for you.

How about at least stating in mathematical terms what you are to prove, and writing as many steps in a first draft of a proof as you can, even though it won't all be right?

 

[agnes1999]

So maybe you aren't expected to use it.

Are there any hints you were given, or any example problems that might be relevant? I need to see something that you do know, or have tried, in order to have a place to start. In addition to the basics of induction, what do you know of number theory and related concepts that might be used here? If I were helping you in person, I would be looking through your text and looking for ideas for you.

How about at least stating in mathematical terms what you are to prove, and writing as many steps in a first draft of a proof as you can, even though it won't all be right?

So k cents of postage can be made using 5 and 7 cents stamps.

I know I must prove the this is true for k ≥ 24


I understand that If you can do it for five consecutive values of k, say for k=24, k=25, k=26, k=27, and k=28, then you can do it for any larger value of k.
So if you let P(k) denote the statement that any integer amount of postage from k to k+4 inclusive can be made using 5 and 7 cent stamps, you can prove that P(k) implies P(k+1).

This is my inductive hypothesis. I am so lost when it comes to writing the aspect of the proof that comes after the hypothesis.

 

[Dr.Peterson]

So k cents of postage can be made using 5 and 7 cents stamps.

I know I must prove the this is true for k ≥ 24

Mathematically, this is, "For any integer k ≥ 24, there exist non-negative integers x and y such that k = 5x + 7y." That's what I was expecting from you. That kind of statement helps clarify the goal, and also helps in stating the inductive hypothesis.

I understand that If you can do it for five consecutive values of k, say for k=24, k=25, k=26, k=27, and k=28, then you can do it for any larger value of k.

This is one good approach to the inductive step; you'll be proving this at that time. (There are, of course, others.)

So if you let P(k) denote the statement that any integer amount of postage from k to k+4 inclusive can be made using 5 and 7 cent stamps, you can prove that P(k) implies P(k+1).

So you're saying (by the word "can") that this part will be easy once you set up the inductive step, right? Or do you really mean "you have to ..."?

This is my inductive hypothesis. I am so lost when it comes to writing the aspect of the proof that comes after the hypothesis.

So, mathematically speaking, you are defining the proposition to be proved as

P(i): For integers k = i, i+1, i+2, i+3, and i+4, there exist non-negative integers x and y such that k = 5x + 7y.​

Your base case then is that P(1), P(2), P(3), P(4), and P(5) are true, right?

And your inductive hypothesis is that P(k) is true, from which you want to prove that P(k+1) is true. Am I right?

At this point, you apply the reasoning that led you to say above, "I understand that If you can do it for five consecutive values of k, say for k=24, k=25, k=26, k=27, and k=28, then you can do it for any larger value of k". What is that reasoning?