Thread: Help finding formula (mathematical induction)

Can someone help me find the formula I need to get started with this problem?

Which amounts of money can be formed using just dimes and quarters?


I thought the formula should be something along the lines of 10x+25x=y but then I got to thinking that maybe the variable should be different with the dime and quarter because they would not always have to be the same.

yeah, they must be of different variable since the number of dimes does not depend on the number of quarters, in particular, number of dimes is not equal to the number of quarters..

That's what I was thinking, would it be something like 10a+25b=n? That doesn't seem to be quite right. Since I know I have to figure it out for the smallest amount I would say 10(1)+25(0)=10, but I don't know where to go from there?

Hello,

Originally Posted by sjenkins

That's what I was thinking, would it be something like 10a+25b=n? That doesn't seem to be quite right. Since I know I have to figure it out for the smallest amount I would say 10(1)+25(0)=10, but I don't know where to go from there?

I don't understand what is wrong with 10a+25b=n... ?

Is there a condition for n ? is it the whole text you've been given ?

Yes, the only other text I have is "prove your answer using a form of mathematical induction". That is why I'm so confused, usually when I have done other induction problems, there has only been one variable, but I'm not sure how to go about solving this with more than one.

Originally Posted by sjenkins

Which amounts of money can be formed using just dimes and quarters?

i wonder why the question is which.. are there choices given or none? if you don't mind, will you write the whole question.. thanks..

Sure, no problem, here is the question as it appears in the book...

Which amounts of money can be formed using just dimes and quarters? Prove your answer using a form of mathematical induction.

Originally Posted by sjenkins

Can someone help me find the formula I need to get started with this problem?

Which amounts of money can be formed using just dimes and quarters?

The common-sense answer is that you can get any multiple of 5¢ apart from 5¢ and 15¢.

To put it more mathematically, the number of cents is of the form 5n, where n is any positive integer apart from 1 or 3.

The proof by induction goes like this. Base cases: the result is true for n=2 (1 dime), n=4 (2 dimes) and n=5 (1 quarter). Inductive step: suppose that n≥4 and that the result is true for n. Then it is true for n+2 (because we can use the result for n and add one dime).

Notice that this is a rather non-standard form of inductive proof. You need to look at more than one base case, and the inductive step goes from n to n+2 instead of from n to n+1. You can get round this by doing two separate inductive arguments, one for even values of n (starting at n=2) and one for odd values (starting at n=5).