Acountry uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. 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.

In order to find the recurrence relation, find first the pattern by writing the terms. 

If one pays a certain amount of pesos (n) , it could be shown as follows:
To pay 1 peso -              then n-1 peso
To pay 2 peso coin-       then n-2 peso if n≥2
To pay 5 peso coin-       then n-5 peso if n≥5
To pay 10 peso coin-     then n-10 peso if n≥10
To pay 5 peso bill-         then n-5 peso if n≥5
To pay 10 peso bill-       then n-10 peso if n≥10
To pay 20 peso bill-       then n-20 peso if n≥20
To pay 50 peso bill-       then n-50 peso if n≥50
To pay 100 peso bill-     then n-100 peso if n≥100

A₀ = 1
The pattern being each new option is part of the recurrence relation. Therefore:
(note: n-1, n-2,... and so on are subscript of A)
 
An = An−1+An−2+An−5+An−10+An-5+ An-10+An−20+An−50+An−100An
An = An−1+An−2+2An−5+2An−10+An−20+An−50+An−100An

Buy this now or get it now