Question

A country 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.

Answer 1

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