Answer to Question #123223 in Discrete Mathematics for Kavee

Question

6. (i) Show that postage of 24 cents or more can be achieved by using only 5-cent and 7-cent stamps.
(ii) c1 = 0 and cn = cn/2 + n2 for all n > 1.
(a) Compute c2,c3,c4 and c5. (b) Prove that cn < 4n2 for all n ≥ 1.

Answer 1

1)for n = 24, 25 , 26, 27 (we explicitly show how these can be achieved)

     24 = 2 * 5 + 2 * 7   

     25 = 5 * 5   

     26 = 1 * 5 + 3 * 7   

     27 = 4 * 5 + 1 * 7  

    Let's assume that the statement holds for all k  such that   n ≥  k ≥ 24.

    Then for n + 1 cents postage case,      if  (n + 1) - 5 = n - 4 ≥ 24 , then by inductive assumption, (n-4) cents can be achieved by using only 5-cents and 7-cents stamps, and hence (n+1) cents can be achieved by using one extra 5-cent stamp as in (n-4) cents case.  if (n-4) < 24 then n must be one of those values : 24 , 25, 25 or 27 (since n ≥ 24 ), and it has been justified in basic step. Hence the statement is true for all n ≥ 24.

2) a) c₂=c₁+2²=4

c₃=c₁+3²=9

c₄=c₂+4²=20

c₅=c₂+5²=29

b)$C_1=0<4, C_2=C_1+1=1<16$

if we suppose $C_k<4k^2$ for k≥2, then:

For k=2n+1 we have

$C_{k+1}=C_n+4n^2<8n^2=2(k+1)^2<4(k+1)^2;$

For k=2n we have

$C_{k+1}=C_n+(2n+1)^2<4n^2+(2n+1)^2=2k^2+2k+1<4(k+1)^2.$