The Art and Craft of Problem Solving

172 CHAPTER 5 ALGEBRA

For the first step, observe that if n > 1, then n < J n2 + 1 < n + 1/ n. The first

inequality is obvious, and the second follows from n (^2) + 1 < n 2 + 2 < (n + 1/ n) 2. Let
us call the sum in question S. Then
S = 1001 + 81 + (^1002) + lh + ... + (^2000) + 81000 ,
where each 8 i lies between 0 and 1/1001. Consequently,
o < 8 1 + lh + ... + 81000 < 1,
so S is not an integer.
Next, we will show that S is a zero of a monic polynomial. More generally, we
shall prove that for all positive integers n, the quantity
Val +Ja2+ ... +JGn
is a zero of a monic polynomial if each ai is an integer that is not a perfect square. We
proceed by induction. If n = 1, the assertion is true becau se y'aI is a zero of the monic
polynomial x^2 - al. Now assume that
Y= Val +Ja2+ ... +JGn
is a zero of the monic polynomial P(x) = x + cr- 1 x'·-^1 + ... +co. We will produce a
monic polynomial that has x = Y + v'an+ 1 as a zero. We have
0= P(y) = P(x-v'an+d = (x-v'an+IY +Cr-I (x-Jan+ly -^1 + ... +co.
Notice that the expansion of each (x -v'an+ I)k term can be separated into terms that
have integer coefficients and terms with coefficients equal to an integer times v'an+ 1.
Thus we have
0= P(x -Jan+d =x +Q(x) + Jan+IR(x),
where Q(x) and R(x) are polynomials with integer coefficients, each of degree at most

r -1. Putting the radicals on one side of the equation yields

x + Q(x) = -Jan+IR(x),

and squaring both sides leads to

x^2 r + lXQ(x) + (Q(x))^2 - an+ 1 (R(x))^2 = O.

The term with highest degree is x^2 r. Since all coefficients are now integers, we have

produced a monic polynomial with x = Y + Jan+ 1 as a zero, as desired. _

Problems and Exercises

5.4.6 Prove that a polynomial of degree n can have at

most n distinct zeros.

5.4.7 Use Problem 5.4.6 to prove a nice application

called the identity principle, which states that if two

degree-d polynomials f(x),g(x) are equal for d + I

different x-values, then the two polynomials are equal.

5.4.8 Prove that if a polynomial has real coefficients,

then its zeros come in complex conjugate pairs; i.e., if

a + hi is a zero, then a -hi is also a zero.