Suppose that you have a large supply of $3$ and $7$ cent stamps. Write a recurrence relation and initial conditions for the number $S_n$ of different ways in which n cents worth of stamps can be attached to an envelope if the order in which the stamps are attached does matter.
[Math] Stamp Problem Homework
discrete mathematics
Best Answer
The ordered case, as previously noted, satisfies the recurrence $$S_{\mathrm{ord}}(n)=S_{\mathrm{ord}}(n-3)+S_{\mathrm{ord}}(n-7).$$
For the unordered case, I give the following hint:
Hint (since this is flagged as homework): We can adjust this recurrence to account for the "order is not important" by adding in a correction term to account for overcounting. So, we have $$S(n)=S(n-3)+S(n-7)-[???].$$ There's quite an elegant reason for this, and I don't want to spoil this for you.
The initial conditions are merely bookkeeping (they can be counted by hand, once you know the depth of the recurrence).