SOLUTION: 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 u

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

RELATED QUESTIONS
Prove that, log(n) >= k.log(2) (Where n >= 2 and "k" denote the number of distinct prime... (answered by richard1234)

1. Let X(k) denote the N-point DFT of the N-point sequence x(n) a) If x(n)... (answered by Fombitz)

Let p(n) and s(n) denote the product and the sum, respectively, of the digits of the... (answered by Edwin McCravy)

For positive integer values of N, let N be defined as: N = 2 + 4 + 6 + ... + N, if N (answered by Edwin McCravy)

Let n!!! denote the product n*(n-3)*(n-6)*...*x where x is either 1, 2, or 3, if n is 1,... (answered by richard1234)

The number of ways a class of n student can elect a president, a vice president, a... (answered by stanbon)

Adenine (A), cytosine (C), thymine (T) and guanine (G) are four main nucleobases found in (answered by ikleyn)

I have the following problem: Let P(n, k) denote the number of permutations of k objects (answered by stanbon)

Prove that one and only one out of n,n+4,n+8,n+12 and n+16 is divisible by 5,where n is... (answered by math_helper)