1.8. EXERCISES 29

Thus p1 − p2 is an integer between 0 and 1, contradicting Theorem 1.7.8. The case thatr1 > r2 cannot occur either by similar reasoning. Thus r1 = r2 and it follows that p1 = p2.

This theorem is called the Euclidean algorithm when a and b are integers. In this case,you would have r is an integer.

1.8 Exercises1. By Theorem 1.7.9 it follows that for a < b, there exists a rational number between a

and b. Show there exists an integer k such that a < k2m < b for some k,m integers.

2. Show there is no smallest number in (0,1) . Recall (0,1) means the real numberswhich are strictly larger than 0 and smaller than 1.

3. Show there is no smallest number in Q∩ (0,1) .

4. Show that if S ⊆ R and S is well ordered with respect to the usual order on R then Scannot be dense in R.

5. Prove by induction that ∑nk=1 k3 = 1

4 n4 + 12 n3 + 1

4 n2.

6. It is a fine thing to be able to prove a theorem by induction but it is even better tobe able to come up with a theorem to prove in the first place. Derive a formula for∑

nk=1 k4 in the following way. Look for a formula in the form An5 +Bn4 +Cn3 +

Dn2 +En+F. Then try to find the constants A,B,C,D,E, and F such that thingswork out right. In doing this, show

(n+1)4 =(

A(n+1)5 +B(n+1)4 +C (n+1)3 +D(n+1)2 +E (n+1)+F)

−(

An5 +Bn4 +Cn3 +Dn2 +En+F),

so some progress can be made by matching the coefficients. When you get youranswer, prove it is valid by induction.

7. Prove by induction that whenever n ≥ 2,∑nk=1

1√k>√

n.

8. If r ̸= 0,1, show by induction that ∑nk=1 a(rk) = a rn+1

r−1 −a rr−1 .

9. Prove by induction that ∑nk=1 k = n(n+1)

2 .

10. Let a and d be real numbers. Find a formula for ∑nk=1 (a+ kd) and then prove your

result by induction.

11. Consider the geometric series, ∑nk=1 ark−1. Prove by induction that if r ̸= 1, then

∑nk=1 ark−1 = a−arn

1−r .

12. This problem is a continuation of Problem 11. You put money in the bank and itaccrues interest at the rate of r per payment period. These terms need a little ex-planation. If the payment period is one month, and you started with $100 then theamount at the end of one month would equal 100(1+ r) = 100+100r. In this the sec-ond term is the interest and the first is called the principal. Now you have 100(1+ r)