## Thursday, November 30, 2006

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