Explore BrainMass

Recurrence Relation

A vending machine accepts only pennies and nickels.
a) Find a recurrence relation for the number of ways to deposit n cents where the order in which coins are deposited matters.
b) What are the initial conditions for the recurrence?
c) Use the recurrence to count the number of ways to deposit 12 cents.

Solution Preview

Let f(n) be the number of ways to deposit n cents.
To find the recurrence relation of f(n), we check f(n) for some small n's.
We use P for penny and N for nickel ( one nickel = 5 penny, one penny = one cent )
f(1)=1, one way: P
f(2)=1, one way: PP
f(3)=1, one ...

Solution Summary

A recurrence relation is investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.