Mathematics for Computer Science

(Frankie) #1

1.9. Good Proofs in Practice 23


teammates for a few minutes and summarize your team’s answers on your white-
board.


Problem 1.7.
Here is a generalization of Problem 1.5 that you may not have thought of:


Lemma 1.9.1. Let the coefficients of the polynomiala 0 Ca 1 xCa 2 x^2 CC
an 1 xm^1 Cxmbe integers. Then any real root of the polynomial is either integral
or irrational.


(a)Explain why Lemma 1.9.1 immediately implies that m

p
kis irrational when-
everkis not anmth power of some integer.


(b)Collaborate with your tablemates to write a clear, textbook quality proof of
Lemma 1.9.1 on your whiteboard. (Besides clarity and correctness, textbook qual-
ity requires good English with proper punctuation. When a real textbook writer
does this, it usually takes multiple revisions; if you’re satisfied with your first draft,
you’re probably misjudging.) You may find it helpful to appeal to the following:
Lemma 1.9.2.If a prime,p, is a factor of some power of an integer, then it is a
factor of that integer.


You may assume Lemma 1.9.2 without writing down its proof, but see if you can
explain why it is true.


Homework Problems


Problem 1.8.
The fact that that there are irrational numbersa;b such thatabis rational was
proved in Problem 1.3. Unfortunately, that proof wasnonconstructive: it didn’t
reveal a specific pair,a;b, with this property. But in fact, it’s easy to do this: let
aWWD


p
2 andbWWD 2 log 23.
We know

p
2 is irrational, and obviouslyabD 3. Finish the proof that thisa;b
pair works, by showing that 2 log 23 is irrational.

Free download pdf