128
Proofs, Induction, and Number Theory
77. Prove that any amount of postage greater than or equal to 2 cents can be built using only 2-cent and 3-cent
stamps.
78. Prove that any amount of postage greater than or equal to 12 cents can be built using only 4-cent and
5-cent stamps.
79. Prove that any amount of postage greater than or equal to 14 cents can be built using only 3-cent and
8-cent stamps.
80. Prove that any amount of postage greater than or equal to 42 cents can be built using only 4-cent and
15-cent stamps.
81. Prove that any amount of postage greater than or equal to 64 cents can be built using only 5-cent and
17-cent stamps.
82. Your bank ATM delivers cash using only $20 and $50 bills. Prove that you can collect, in addition to $20,
any multiple of $10 that is $40 or greater.
Exercises 83–84 require familiarity with ideas from calculus. Exercises 1–26 give exact formulas for the sum
of terms in a sequence that can be expressed as ∙
n
m=1
f (m). Sometimes it is difficult to find an exact expression
for this summation, but if the value of f (m) increases monotonically, integration can be used to find upper and
lower bounds on the value of the summation. Specifically,
3
n
0
f (x)dx ≤ ∙
n
m=1
f (m) ≤ 3
n+1
1
f (x)dx
Using the following figure, we can see (on the left) that 3
n
0
f (x)dx underestimates the value of the summation
while (on the right) 3
n+1
1
f (x)dx overestimates it.
0
1
2
3
4
f(1) f(2) f(3) f(4)
f(x)
1
2
3
4
5
f(1) f(2) f(3) f(4)
f(x)
83. Show that 3
n
0
2x dx ≤ ∙
n
m=1
2m ≤ 3
n+1
1
2x dx (see Exercise 2).
84. Show that 3
n
0
x
2
dx ≤ ∙
n
m=1
m
2
≤ 3
n+1
1
x
2
dx (see Exercise 7).