Results 1 to 6 of 6

Math Help - Proof by induction

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    6

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by franklina View Post
    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".
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    You need to make sure you aren’t dealing with negative amount of dollars as well! For example

    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Last edited by JaneBennet; December 23rd 2007 at 03:43 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by JaneBennet View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum