# Proof by induction

• December 21st 2007, 06:28 AM
franklina
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!
• December 21st 2007, 08:31 AM
ThePerfectHacker
Quote:

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,
$5x+9y = N$ have negative integer solutions $x,y$ for $N\geq 31$.
Note that $\gcd (5,9) = 1$ thus, it is possible to always solve this equation for integers, though they might not necessary be non-negative.
Now $5(2) + 9(-1) = 1 \implies 5(2N)+9(-N) = N$.
By using linear diophantine equations theorem all the solutions are given by,
$x = 2N - 9t \mbox{ and } y = - N + 9t \mbox{ for }t\in \mathbb{Z}$.
Since we want non-negative solution we require that,
$x,y\geq 0 \implies t \leq \frac{2}{9}N \mbox{ and }t\geq \frac{1}{9}N$
Thus, $\frac{1}{9}N \leq t \leq \frac{2}{9}N \implies N \leq 9t \leq 2N$

Therefore, the problem comes down to: "If $N\geq 31$ then between $N$ and $2N$ there exists a multiple of 9 between them".
• December 21st 2007, 03:56 PM
JaneBennet
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.
• December 22nd 2007, 02:02 PM
ThePerfectHacker
You can do it like this.

If $n= 5k$ then you can just use 5 dollars to get the amount.

If $n=5k+1$ then $n-1$ 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 $n=5k+2$ then $n-2$ 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 $n=5k+3$ then $n-3$ can be expressed in just 5's. You can write 3 as 2*9 - 2*5 and same idea follows.

If $n=5k+4$ then 4 can be expressed as 9 - 5 and use the same idea.
• December 23rd 2007, 03:29 AM
JaneBennet
You need to make sure you aren’t dealing with negative amount of dollars as well! For example

Quote:

Originally Posted by ThePerfectHacker
If $n=5k+2$ then $n-2$ 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 $n=5k+1$, 1 is actually 2×5 − 9, so you need at least one 9-dollar bill in your $n-1$. Either that or 1 = 4×9 − 7×5, meaning you need at least seven 5-dollar bills.
• December 23rd 2007, 08:30 AM
ThePerfectHacker
Quote:

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.