Explore BrainMass

Recurrence Relation

This content was STOLEN from BrainMass.com - View the original, and get the solution, here!

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.

© BrainMass Inc. brainmass.com September 20, 2018, 12:43 pm ad1c9bdddf - https://brainmass.com/math/recurrence-relation/recurrence-relation-vending-machine-110996

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.