How to find a recurrence relation for $F(n)$ the number of ways to make n cents change using only pennies (4 cents), nickels(5cents), and dimes(10cents) and ordering matters.
There are three exclusive case here
- Start with pennies then new subproblem is $F(n-4)$
- Start with nickels then new subproblem is $F(n-5)$
- Start with dimes then new subproblem is $F(n-10)$
$$F(n) = F(n-4)+ F(n-5) + F(n-10) $$
Is there any other way to solve this problem. The above method is ok but seems like magic to beginner. Is there any systematic approach to solve this problem?
Problem is also available on https://math.stackexchange.com/questions/248853/how-to-find-recurrence-relation-for-this-problem