Discrete Mathematics for Computer Science

72 CHAPTER 1 Sets, Proof Templates, and Induction

cents or greater, we conjecture that all amounts except 1, 2, 4, 5, 7, 8, 10, and 13 cents are

possible.

We conjectured that all values starting at 14 are possible, so we handle all n < 14

separately. We noted that 0, 3, 6, 8, 9, 11, and^12 cents are all possible. Amounts of 1, 2,

4, 5, 7, 8, 10, or 13 cents are impossible: To get any of those amounts, one would need to

use, at most, 4 stamps (why?), and we can list all the possible combinations of 0-4 stamps

to show that none add up to 1, 2, 4, 5, 7, 8, 10, or^13 cents.

Let

T = {n e N: n > 14 and n = k .3 + .8 for some k, 1 E NJ

We must then prove that every natural number n > 14 is in T.

(Base step) After some experimentation, we decide the base cases are 14, 15, and 16.

Sincel4 = 2.3+ 1.8, 15 = 5.3+0.8, andl6 =0.3+2.8,wehavel4,15,16 G T.

(Inductive step) Let n > 14, and assume that 14, 15, 16. n - 1 E T. Now, prove

that n E T.

Since 14, 15, and^16 are base cases, every possible value for n that is not a base case

and is greater than or equal to 14 is also greater than or equal to 17. For n > 17, we have

n - 3 > 14. So, by the inductive hypothesis, for some k, I E N, n - 3 = k 3 + 1. 8. Then,

n = (n-3)+3 = k-3+1.8+3 = (k+1).3+8.I

So, n E '-, as desired.

By the Strong Form of Mathematical Induction, T = {n E N : n > 14}. 0

There are some other values for which Oz can make postage-for example, 3, 6, 8, 9,

11, and 12. When we looked carefully at the inductive step, we saw we would have to be

able to go back three from any n for which we were proving the postage amount could be

made. We were then more clear on what the base cases would need to be. Consequently,

the base step proved postage can be made for n = 14, 15, and 16. It is not unusual that the

base cases are identified by trying the inductive step of the proof. Note that in the proof

of the inductive case above, before applying the inductive hypothesis to n - 3, we checked

that n - 3 > no. Not making that check is a very easy way to make an error. In this case,

had we not made that check, we might have started with n = 12, asserted that n - 3 = 9

was in T, and proceeded as with the inductive case above-and we would have "proved"

something that was actually false.

1.10.2 Application: Algorithm to Compute Powers

Suppose you want to compute xn for some nonzero real number x and some natural number

n. One way is to multiply together n copies of x, a task that requires n - 1 multiplications.

Are there faster ways to complete this computation? We will prove that the following al-

gorithm computes xn using far fewer multiplications for large values of n.