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 ?