## 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$.

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.

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

3. again the statement follows from the intermediate value theorem

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].