Exponents Away. Topic: Algebra/Calculus. Level: AIME/Olympiad.

Problem: (Problem-Solving Through Problems - 6.5.12) Suppose $ n $ is a nonnegative integer and

$ f_n(x) = c_0e^{r_0x}+c_1e^{r_1x}+\cdots+c_ne^{r_nx} $,

where $ c_i $ and $ r_i $ are real numbers. Prove that if $ f $ has more than $ n $ zeros in $ \mathbb{R} $, then $ f(x) \equiv 0 $.

Solution: First, we add the claim that $ f_n(x) = 1 $ can occur for at most $ n+1 $ distinct $ x $.

We proceed by induction. For $ n = 0 $, we have $ f_0(x) = c_0e^{r_0x} $ which we know is not zero unless $ c_0 = 0 $, so if it has a root it must be identically $ 0 $. It also takes the value $ 1 $ at most once because it is monotonic. Now suppose both hypotheses are true for some nonnegative integer $ k $. We want to show that

$ f_{k+1}(x) = c_0e^{r_0x}+c_1e^{r_1x}+\cdots+c_ke^{r_kx}+c_{k+1}e^{r_{k+1}x} $

has at most $ k+1 $ zeros (except when $ c_i = 0 $ for all $ i $) and takes the value $ 1 $ at most $ k+2 $ times. If $ c_{k+1} = 0 $, we apply the inductive hypothesis and it is trivially true, so assume $ c_{k+1} \neq 0 $. From $ f_{k+1}(x) = 0 $, we get

$ c_0e^{r_0x}+c_1e^{r_1x}+\cdots+c_ke^{r_kx} = -c_{k+1}e^{r_{k+1}x} $.

Letting $ b_i = -\frac{c_i}{c_{k+1}} $ and $ q_i = r_i-r_{k+1} $ for $ i = 0, 1, \ldots, k $, we obtain

$ b_0e^{r_0x}+b_1e^{r_1x}+\cdots+b_ke^{r_kx} = 1 $.

By our inductive hypothesis, we know this occurs at most $ k+1 $ times, proving that $ f_{k+1} $ has at most $ k+1 $ zeros or is identically $ 0 $.

Now we want to show that $ f_{k+1}(x) = 1 $ at most $ k+2 $ times. Suppose $ f_{k+1}(x) = 1 $ for $ x_1 < x_2 < \ldots < x_m $ for $ m > k+2 $. Then, by Rolle's Theorem, we have

$ f_{k+1}^{\prime}(x) = c_0r_0e^{r_0x}+c_1r_1e^{r_1x}+\cdots+c_kr_ke^{r_kx}+c_{k+1}r_{k+1}e^{r_{k+1}x} = 0 $

between each consecutive pair of $ x_i $'s, giving us $ m-1 > k+1 $ pairs. But by what we just proved for $ f_{k+1} $ having at most $ k+1 $ zeros, we know $ f_{k+1}^{\prime}(x) = 0 $ at most $ k+1 $ times, since $ f_{k+1}^{\prime} $ is in the same family of functions. Hence $ f_{k+1}(x) = 1 $ for at most $ k+2 $ distinct $ x $, completing the induction.

Therefore, we conclude that $ f_n(x) $ has at most $ n $ zeros or is identically $ 0 $.

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

Comment: A pretty tough problem, took a couple of looks at smaller cases to determine the method with which to solve it. The key is looking for the inductive step, somehow reducing the $ k+1 $ case to the $ k $ case. Adding in the extra condition might not have been necessary but it made it easier to move from case to case. Here's a "flow chart" of what proves what.

$ f_k(x) = 0 $ for at most $ k $ values or is identically $ 0 $ --> $ f_k(x) = 1 $ for at most $ k+1 $ values --> $ f_{k+1}(x) = 0 $ for at most $ k+1 $ values or is identically $ 0 $ --> $ f_{k+1}(x) = 1 $ for at most $ k+2 $ values.

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

Practice Problem: Show that $ x^3-3x+b $ cannot have more than one zero in $ [-1,1] $, regardless of the value of $ b $.