Bookmark Suppose you have books...post office problem Question Details Suppose y

Question

Bookmark Suppose you have books...post office problem
Question Details
Suppose you have books of 1c, 2c, and 5c stamps. You need to mail a letter that requires a postage of n cents. The question is: In how many ways can you affix on the envelope any of the stamps that you have (order matters), such that their sum will be n cents?

Note, order matters (1, 2, 1) differs from (2, 1,1 ) et cetera.

a. Derive the general recursion relation, along with the initial conditions that are needed.
b. Give the actual answer for n =10.

Explanation / Answer

If the first stamp is a 5c, then there are f(n-5) such sequences.
Hence, f(n) = f(n-1) + f(n-2) + f(n-5). Also, if n<5 then no 5 stamp can be used, so in those cases, f(n) = f(n-1)+f(n-2). Also, trivially, f(1) = 1, f(2) = 2, so that f(3) = 3, f(4) = 5. Use these recursively to get f(5), f(6),...,f(10).

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.