Mathematics for Computer Science

2.4. Factoring into Primes 31

Exam Problems

Problem 2.5.
The (flawed) proof below uses the Well Ordering Principle to prove that every
amount of postage that can be paid exactly, using only 10 cent and 15 cent stamps,
is divisible by 5. LetS.n/mean that exactlyncents postage can be paid using only
10 and 15 cent stamps. Then the proof shows that

S.n/ IMPLIES 5 jn; for all nonnegative integersn: (*)

Fill in the missing portions (indicated by “... ”) of the following proof of (*), and
at the final line point out where the error in the proof is.

LetCbe the set ofcounterexamplesto (*), namely

CWWDfnjS.n/andNOT.5jn/g

Assume for the purpose of obtaining a contradiction thatCis nonempty.

Then by the WOP, there is a smallest number,m 2 C. ThenS.m10/

orS.m15/must hold, because themcents postage is made from 10

and 15 cent stamps, so we remove one.

So supposeS.m10/holds. Then 5 j.m10/, because...

But if 5 j.m10/, then 5 jm, because...

contradicting the fact thatmis a counterexample.

Next supposeS.m15/holds. Then the proof form 10 carries

over directly form 15 to yield a contradiction in this case as well.

Since we get a contradiction in both cases, we conclude thatC must

be empty. That is, there are no counterexamples to (*), which proves

that (*) holds.

What was wrong/missing in the argument? Your answer should fit in the line
below.

Problems for Section 2.3

Practice Problems

Problem 2.6.
The Fibonacci numbers
0;1;1;2;3;5;8;13;:::

are defined as follows. LetF.n/be thenth Fibonacci number. Then