Results 1 to 4 of 4

Math Help - find a recurrence relation

  1. #1
    Member
    Joined
    May 2008
    Posts
    94

    find a recurrence relation

    Find a recurrence relation for the number of ways to pay a bill of n dollars if the order in which the coins and bills are paid matters.
    We have "coins" of 1, 2, 5, 10$ and "bills" of 5, 10, 20, 50 and 100$.

    How to begin doing this sum?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Okay, let's call a_n the number of ways in which you can the bill of n dollars.

    Note that if we want to pay a bill of n+1 dollars we can add a coin of a dollar to n dollars, this can be done in a_n ways, now if we want to add a coin of 2 dollars this can be done in a_{n-1} ways (since we need n-1 dollars), and so on...

    Summing all the possibilities:

    a_{n+1}=a_{n}+a_{n-1}+2a_{n-4}+2a_{n-9}+a_{n-19}+a_{n-49}+a_{n-99} (1)

    Now for this to always make sense we define a_n=0 if n<0 and a_{0}=1 (there's only one way of paying nothing) and then a_{n+1} is defined by (1) if n\geq{0}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2008
    Posts
    17
    Quote Originally Posted by PaulRS View Post
    now if we want to add a coin of 2 dollars this can be done in a_{n-1} ways (since we need n-1 dollars), and so on...

    Summing all the possibilities:

    a_{n+1}=a_{n}+a_{n-1}+2a_{n-4}+2a_{n-9}+a_{n-19}+a_{n-49}+a_{n-99}
    Wow, but I got some doubts.... the derivation is quite tough for me....


    How this works?
    now if we want to add a coin of 2 dollars this can be done in a_{n-1} ways (since we need n-1 dollars), and so on...
    well I got it about 2a_{n-4} since there are two ways to pay a 5 dollar, by coin and a bill....

    I think it is about assumption that to pay a bill of n we need a_{n} so we need a_{n-1} ways to pay a bill of n-1


    but still I need some explanation.... am I right in my thinking....
    cheers...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by natarajchakraborty View Post
    Wow, but I got some doubts.... the derivation is quite tough for me....


    How this works?


    well I got it about 2a_{n-4} since there are two ways to pay a 5 dollar, by coin and a bill....

    I think it is about assumption that to pay a bill of n we need a_{n} so we need a_{n-1} ways to pay a bill of n-1



    but still I need some explanation.... am I right in my thinking....
    cheers...
    Forget about the bill, the only thing you want is to know in how many ways you can hand in n+1 dollars using that type of coins and notes.

    If we want to GIVE A $1 coin at the end (for we care about the order), we need to have $N otherwise will NOT be giving $N+1, but we can give $N dollars in a_n ways, thus if the thing you want to hand in last is a 1 dollar coin you can do this in a_n ways

    Now the other cases (according to what you want to give last) are very similar and so, by the sum rule we have what I'd posted
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 9
    Last Post: September 24th 2011, 07:19 AM
  2. find a recurrence relation question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 07:03 PM
  3. How to find the limit of recurrence relation
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 30th 2009, 07:36 AM
  4. Find solution to a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 20th 2009, 11:17 AM
  5. find a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 27th 2008, 08:08 AM

Search Tags


/mathhelpforum @mathhelpforum