Wednesday, May 10, 2006

Cos It's A Polynomial. Topic: Algebra/Polynomials/Trigonometry. Level: AIME/Olympiad.

Problem: (Problem-Solving Through Problems - 6.2.7) Prove that the trigonometric polynomial

$ a_0+a_1\cos{x}+\cdots+a_n\cos{nx} $,

where the coefficients are all real and $ |a_0|+|a_1|+\cdots+|a_{n-1}| \le a_n $, has at least $ 2n $ zeros in the interval $ [0, 2\pi) $.

Solution: Let $ f_n(x) = a_0+a_1\cos{x}+a_2\cos{2x}+\cdots+a_n\cos{nx} $ and $ k $ be a positive integer. We examine $ f_n\left(\frac{(2k-1) \pi }{n}\right) $ and $ f_n\left(\frac{2 k \pi}{n}\right) $.

$ f_n\left(\frac{(2k-1) \pi}{n}\right) = a_0+a_1\cos{\frac{(2k-1) \pi}{n}+\cdots-a_n $

and

$ f_n\left(\frac{2 k \pi}{n}\right) = a_0+a_1\cos{\frac{2 k \pi}{n}}+\cdots+a_n $.

Since $ |a_0|+|a_1|+\cdots+|a_{n-1}| > a_0+a_1\cos{x}+\cdots+a_{n-1}\cos{(n-1)x} $ (strict inequality because not all of the cosines can equal $ \pm 1 $ at the same time - unless $ n = 0,1 $ which can be handled easily), we have

$ f_n\left(\frac{(2k-1) \pi}{n}\right) < |a_0|+|a_1|+\cdots+|a_{n-1}|-a_n \le 0 $

and

$ f_n\left(\frac{2 k \pi}{n}\right) > -(|a_0|+|a_1|+\cdots+|a_{n-1}|)+a_n \ge 0 $.

So the function alternates between postive and negative. Therefore, by the Intermediate Value Theorem, $ f_n(x) $ must have a zero between $ \frac{(2k-2) \pi}{n} $ and $ \frac{(2k-1) \pi}{n} $ and between $ \frac{(2k-1) \pi}{n} $ and $ \frac{2 k \pi}{n} $ for any positive integer $ k $. But since $ k $ can range from $ 1 $ to $ n $, this means there must be at least $ 2n $ zeros, as desired. QED.

--------------------

Comment: The Intermediate Value Theorem is a good way of finding zeros; find one negative value and one positive one and there must exist a zero between them (if the function is continuous). The contrived condition on the problem also makes us think this.

--------------------

Practice Problem: (Problem-Solving Through Problems 6.2.4) Suppose $ f: [0,1] \to [0,1] $ is continuous. Prove that there exists a number $ c $ in $ [0,1] $ such that $ f(c) = c $.

4 comments:

  1. Suppose f(c) - c has no zeroes in the interval [0, 1]. Then it must be either always negative or always positive in the interval. Particularly, either f(0) < 0 or f(1) > 1. Contradiction! Hence it has a zero.

    ReplyDelete
  2. Follow-up: consider f:(0, 1) --> (0, 1). Does there still exist such a c? =)

    ReplyDelete
  3. again the statement follows from the intermediate value theorem

    ReplyDelete
  4. Actually, there doesn't necessarily exist such a c. For instance, f(x) = (1/2)x + 1/2. We have 1 > f(x) > x > 0 for all x in (0,1). The problem in extending the proof given above is, as an example, if f(1)-1 = 0 and f(x)-x > 0 for all other x in [0,1].

    ReplyDelete