Question 1147147: Let T(n) denote the number of distinct ways that a postage of n
cents, where n ≥ 4 and n is even, can be made by 4-cent and 6-cent stamps.
For example, if n = 12, then we can use 3 4-cent stamps or 2 6-cent stamps,
and there are no other possible ways. So T(12) = 2. Give a recursive solution to compute T(n) for n ≥ 4 and n is even.
Answer by greenestamps(13200)   (Show Source):
You can put this solution on YOUR website!
2: We can't make 2 cents with combinations of 4 and 6. T(2) = 0
4: We can make 4 cents only one way with 4 and 6 -- one 4-cent stamp. T(4) = 1
6: We can make 6 cents only one way with 4 and 6 -- one 6-cent stamp. T(6) = 1
8: We can make 8 cents only by adding a 4-cent stamp to an earlier total of 4 cents, or by adding a 6-cent stamp to an earlier total of 2 cents. T(8) = T(4)+T(2) = 1+0 = 1.
10: We can make 10 cents only by adding a 4-cent stamp to an earlier total of 6 cents, or by adding a 6-cent stamp to an earlier total of 4 cents. T(10) = T(6)+T(4) = 1+1 = 2.
12: We can make 12 cents only by adding a 4-cent stamp to an earlier total of 8 cents, or by adding a 6-cent stamp to an earlier total of 6 cents. T(12) = T(8)+T(6) = 1+1 = 2.
14: We can make 14 cents only by adding a 4-cent stamp to an earlier total of 10 cents, or by adding a 6-cent stamp to an earlier total of 8 cents. T(14) = T(10)+T(8) = 2+1 = 3.
Clearly the pattern will continue. So a recursive formula for T(n) -- valid of course only for even values of n -- is
T(n) = T(n-4)+T(n-6)
Note that it might be better, since the formula is only valid for even integers, to write it as
T(2n) = T(2n-4)+T(2n-6)
The first several terms of the sequence, found recursively, are
0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,...
|
|
|
