[Math] Recurrence relation question

discrete mathematicsrecurrence-relations

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos.

a) Find a recurrence relation for the number of ways to pay a bill of n pesos if the order in which the coins and bills are paid matters.

b) How many ways are there to pay a bill of 17 pesos, where the order in which coins and bills are paid matters ?

my try was :

when i pay $ n$ pesos i either

  • pay 1 pesos coin , then n-1 pesos
  • pay 2 pesos coin , then n-2 pesos if n $\ge$ 2
  • pay 5 pesos coin , then n-5 pesos if n $\ge$ 5
  • pay 10 pesos coin , then n-10 pesos if n $\ge$ 10
  • pay 5 pesos bill , then n-5 pesos if n $\ge$ 5
  • pay 10 pesos bill , then n-10 pesos if n $\ge$ 10
  • pay 20 pesos bill , then n-20 pesos if n $\ge$ 20
  • pay 50 pesos bill , then n-50 pesos if n $\ge$ 50
  • pay 100 pesos bill , then n-100 pesos if n $\ge$ 100

$a_0 = 1$

so i have $ a_n = a_{n-1} + a_{n-2} + 2a_{n-5} + 2a_{n-10} + a_{n-20} + a_{n-50} + a_{n-100} $

I didn't get (b) right. so what's wrong with my solution ?

Best Answer

Your recurrence relation is correct. The answer to (b) part is 9494.

The following are the first 18 terms(0-17) :

1 | 1 | 2 | 3 | 5 | 10 | 17 | 31 | 54 | 95 | 171 | 302 | 539 | 955 | 1694 | 3011 | 5343 | 9494

I used the following C program to generate these :

#include <stdio.h>
#include <stdlib.h>
#define TERM 17
int main()
{
    /* code */
    int a[20]={1,1,2,3,5};

    int i=5;

    while(i <= TERM)
    {
        if((i-10) >= 0)
        {
            a[i]=a[i-1] + a[i-2] + 2*a[i-5] + 2*a[i-10];
        }
        else
        {
            a[i]=a[i-1] + a[i-2] + 2*a[i-5];
        }
        i++;
    }
    for (int j = 0; j<= TERM; ++j)
    {
        printf("%d | ",a[j]);
    }
    return 0;
}
Related Question