Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
What is the trouble? –  Bombyx mori Nov 12 '12 at 0:56
    
I know you have to set the initial conditions so that S0 = 3, and S1 = 7. But I do not know how to set up the equation after that. –  MKZ Nov 12 '12 at 0:58
    
Let us set up the reverse recurrence scheme: $S_{n}=S_{n-7}+S_{n-3}$. Your set up makes little sense as $0,1$ cents has no choice at all - they are impossible. –  Bombyx mori Nov 12 '12 at 1:01
    
Note: order does not matter. Hence e.g. $S_{10}=1 \neq 2=S_3+S_7$. –  Douglas S. Stones Nov 12 '12 at 1:03

2 Answers 2

up vote 1 down vote accepted

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).

share|improve this answer

If you want to put $n$ cents worth of stamps, you can either put one $7$ cent stamp and $n-7$ cents worth of stamps (i.e. $S_{n-7}$), provided that $n \geq 7$, or one $3$ cent stamp and $n-3$ cents worth of stamps (i.e. $S_{n-3}$), provided that $n \geq 3$. As far as initial conditions are concerned, you just have to analyse what is going on for $n < 7$, which should be fairly easy.

share|improve this answer
    
So for all n>= 7, Sn = 7+S(n-7) and for all n>=3, Sn = 3+S(n-3)? How would that work for n= 4? You can't have use a 3 cent stamp and then have .01$ of another. –  MKZ Nov 12 '12 at 1:04
1  
Actually, I did not see the part where you say that the order does not matter. However, for the ordered case, the relation would be for $n \geq 7, S_n = S_{n-7} + S_{n-3}$. –  beauby Nov 12 '12 at 1:06
    
Sorry, I edited the original question. Order does matter –  MKZ Nov 12 '12 at 1:08
    
No, $S(n) = S(n-3) + S(n-7)$ for $n\ge 7$. Smaller than that you do by hand. Note however that $S(0)=1$. And I guess this is ordered, because the choice in the recursion (take 3 or 7) fixes the value of the first stamp, etc. –  Hendrik Jan Nov 12 '12 at 1:11
    
Can you work out why this is true? –  MKZ Nov 12 '12 at 1:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.