Thread: Proof by induction

I would appreciate help with a question form OCR book further pure 1
"An emerging currency has two kinds of bank note, one for 5 schenkels and one for 9 schenkels. Prove by induction that every account greater than 31 schenkels can be paid without change by using the 5 schenkel and 9 schenkel notes/"

My only ideas were to use the fact that it works for 32 up to 37 and say that every number greater that 31 is made up by one of those plus a multiple of five. But this is quite unmathematical.
Any ideas would be greatly appreciated!

Originally Posted by franklina

I would appreciate help with a question form OCR book further pure 1
"An emerging currency has two kinds of bank note, one for 5 schenkels and one for 9 schenkels. Prove by induction that every account greater than 31 schenkels can be paid without change by using the 5 schenkel and 9 schenkel notes/"

My only ideas were to use the fact that it works for 32 up to 37 and say that every number greater that 31 is made up by one of those plus a multiple of five. But this is quite unmathematical.
Any ideas would be greatly appreciated!

We need to prove the equation,
have negative integer solutions for .
Note that thus, it is possible to always solve this equation for integers, though they might not necessary be non-negative.
Now .
By using linear diophantine equations theorem all the solutions are given by,
.
Since we want non-negative solution we require that,

Thus,

Therefore, the problem comes down to: "If then between and there exists a multiple of 9 between them".

Isn’t this problem supposed to be done using proof by induction? This is my method.

32 = 1×5 + 3×9
33 = 3×5 + 2×9
34 = 5×5 + 1×9
35 = 7×5 + 0×9

Now assume that for some integer n ≥ 35 this amount in schenkels can paid using notes of 5 and 9 schenkels. Thus

n = 5x + 9y

Now, either y > 0 or y = 0. If y > 0, we take away 1 9-schenkel note and add 2 5-schenkel ones to make the next higher amount, so

n+1 = 5(x+2) + 9(y−1)

If y = 0, x must be at least 7 since n ≥ 35. In this case, we make the next higher amount by taking away 7 5-schenkel notes and adding 4 9-schenkel ones:

n+1 = 5(x−7) + 9(y+4)

Hence, by induction, all amounts higher than 31 schenkels can be paid using only the given denominations.

You can do it like this.

If then you can just use 5 dollars to get the amount.

If then can be expressed just in 5 dollars. You can write 1 as 9 - 2*5 so n-1 is now expressed in term of 5's and 9's.

If then can be expressed just in 5 dollars. You can write 2 as 3*9 - 5*5 so n-2 is expressed in terms of 5's and 9's.

If then can be expressed in just 5's. You can write 3 as 2*9 - 2*5 and same idea follows.

If then 4 can be expressed as 9 - 5 and use the same idea.

You need to make sure you aren’t dealing with negative amount of dollars as well! For example

Originally Posted by ThePerfectHacker

If then can be expressed just in 5 dollars. You can write 2 as 3*9 - 5*5 so n-2 is expressed in terms of 5's and 9's.

In other words, with your pool of notes making up the amount n−2, you are adding 3 9-dollar bills and taking away 5 5-dollar bills. For this, you need to have at least five 5-dollar bills in the first place. If k = 3, for instance, this won’t work. You can’t turn $15 into $17 by adding three 9-dollar bills and taking away five 5-dollar ones – this would leave you with a “negative” amount of 5-dollar bills.

And if negative amounts are allowed, the whole problem will be trivial because then any integer amount can be made up by any integer combination of 5 and 9.

BTW, for , 1 is actually 2×5 − 9, so you need at least one 9-dollar bill in your . Either that or 1 = 4×9 − 7×5, meaning you need at least seven 5-dollar bills.

Originally Posted by JaneBennet

You need to make sure you aren’t dealing with negative amount of dollars as well! For example

I know. That is why you are starting from a sufficiently high amount, I should have mentioned this but I assumed it was clear.