Consider the polynomials \[f(x) =\sum_{k=1}^{n}a_{k}x^{k}\quad\text{and}\quad g(x) =\sum_{k=1}^{n}\frac{a_{k}}{2^{k}-1}x^{k},\]where $a_{1},a_{2},\ldots,a_{n}$ are real numbers and $n$ is a positive integer. Show that if 1 and $2^{n+1}$ are zeros of $g$ then $f$ has a positive zero less than $2^{n}$.
Problem
Source: USA TST 2005, Problem 4
Tags: algebra, polynomial, algebra unsolved
RIP
28.10.2006 10:12
It's easy to see that $f(x)=g(2x)-g(x).$ Suppose that for any $x\in(0;2^{n})$ f(x)>0. Then $g(2^{n+1})\ge g(2^{n})>g(2^{n-1})>g(2^{n-2})>\ldots$, i.e. $g(2^{n+1})>g(0)$.Contradiction. Similarly if f(x)<0.
OHO
29.10.2006 12:58
But $f(a)$ can be $>0$ and $f(b)$ can be $<0$ for $a,b\in (0,2^{n})$
epitomy01
11.12.2007 10:40
Nice problem. For convenience let's rewrite it: let $ f(x) = \sum_{1\le i \le n} (2^k - 1)a_{k}x^k, g(x) = \sum_{1 \le i \le n} a_{k}x^k$. Lemma: $ \sum_{0 \le i \le n} f(2^i) = g(2^{n + 1}) - g(1)$. Proof: Since $ f(2^i) = \sum_{1 \le j \le n} a_{j}(2^j - 1)(2^{ij})$, the coefficient of $ a_j$ in $ \sum_{0 \le i \le n} f(2^i)$, is equal to: $ (2^j - 1)* \sum_{1\le k \le n} (2^{j})^k = (2^j - 1) * \frac { (2^j)^{n + 1} - 1}{2^j - 1} = (2^j)^{n + 1} - 1$. Therefore, $ \sum_{0 \le i \le n} f(2^i) = \sum_{0 \le i \le n} a_{i} (2^{i(n + 1)} - 1) = \sum_{0 \le i \le n} a_{i} (2^{n + 1})^i - \sum_{0 \le i \le n} a_{i} = g(2^{n + 1}) - g(1)$. Since $ g(2^{n + 1}) = g(1) = 0$, using Lemma: $ f(2^0) + f(2^1) + ... + f(2^n) = 0$ (*). Suppose that $ f(x)$ does not have any zero between $ 0$ and $ 2^{n}$. If, for some $ i$ ,$ 1 \le i \le n$, $ f(2^{i - 1})$ and $ f(2^{i})$ have different signs, then $ f$ has a zero between $ 2^{i - 1}$ and $ 2^{i}$, a contradiction. So $ f(1), f(2) ... f(2^n)$ all have the same sign, and apart from $ f(2^n)$, they are non-zero. But then $ f(1) + f(2) + ... + f(2^n)$ must also be non-zero, which is in direct contradiction with (*).
epitomy01
11.12.2007 10:55
@ OHO: 'RIP's solution is still correct. Since $ f(x)$ is continuous, if $ f(a) < 0, f(b) >0$ or if $ f(a) < 0, f(b) > 0$, then there is a zero between $ a,b$, which also gives the desired contradiction.
brian22
18.04.2016 04:36
So $f(x)+g(x)=g(2x)$. This is rather trivial to prove.
Now note that $f(1)+g(1)=f(1)=g(2)$, $f(2)+g(2)=f(1)+f(2)=g(4)$, ... $f(2^n)+g(2^n)=f(1)+f(2)+f(4)+\cdots+f(2^n)=g(2^{n+1})=0$. Since the sum, and thus the average, of all the $f$ values is $0$, either they are all $0$ -- in which case $f(1)=0$ and we are done -- or one of them is positive and another is negative. However, by the intermediate value theorem, that implies that there is some number $c$ which lies strictly between the two x-values such that $f(c) = 0$, so since any possible bounding x-values are at most $2^n$, we know that $c < 2^n$, so we have a root of $f$, as desired.
lifeisgood03
10.06.2019 21:23
Note that \begin{align*} 0=g(2^{n+1})-g(1)&=\sum_{k=1}^{n}\frac{a_{k}}{2^{k}-1}(2^{k(n+1)}-1) \\ &=\sum_{k=1}^{n}\frac{a_{k}}{2^{k}-1}(2^{k}-1)(1+2^{k}+2^{2k}+\dots+ 2^{nk}) \\ &=\sum_{k=1}^n a_k (1+2^k+2^{2k}+\dots +2^{nk}) \\ &=f(1)+f(2)+f(4)+\dots+f(2^n) \end{align*} Either all of the $n+1$ terms of $f(1)+f(2)+f(4)+\dots+f(2^n)$ are zero, in which case we can just choose 1 as the root, or there exist two terms which differ in sign. Then, since $f$ is a polynomial, which is continuous, by the Intermediate Value Theorem, there must exist a number strictly between those two terms which is a root of $f$. Since the terms are in the interval $[1, 2^n]$, a number strictly between two terms is in $(1, 2^n)\subset (0, 2^n)$, which is the desired interval, so we're done.