$ f(x)$ is a given polynomial whose degree at least 2. Define the following polynomial-sequence: $ g_1(x)=f(x), g_{n+1}(x)=f(g_n(x))$, for all $ n \in N$. Let $ r_n$ be the average of $ g_n(x)$'s roots. If $ r_{19}=99$, find $ r_{99}$.
Problem
Source: Recursively defined polynomials
Tags: algebra, polynomial, algebra proposed
03.11.2008 22:39
The sequence $ r_n$ is constant, so $ r_{99}= 99$ as well. To see this we will use a simple formula for $ r_n$: If $ p(x) = \alpha_d x^d + \alpha_{d-1}x^{d-1} + \ldots$ is a polynomial of degree $ d$, then the sum of its roots is $ -\alpha_{d-1}/\alpha_d$ and the average is $ r = -\frac{\alpha_{d-1}}{d \alpha_d}$. Let $ f(x) = a_m x^m + a_{m-1}x^{m-1} + \ldots +a_1 x + a_0$. For a fixed but arbitrary $ n$, let us write $ g_n(x) = c_N x^N + c_{N-1} x^{N-1} + \ldots$ $ g_{n+1}(x) = d_M x^M + d_{M-1} x^{M-1} + \ldots$. We have $ g_{n+1}(x) = f(g_n(x))$ so \begin{align*} d_M x^M + d_{M-1}x^{M-1} + \ldots & = & \\ & = & a_m(c_N x^N + c_{N-1}x^{N-1} + \ldots)^m + a_{m-1}(c_N x^N + c_{N-1}x^{N-1}+\ldots)^{m-1} + \ldots \end{align*} The top coefficient $ d_M$ is easy to identify: the largest power of $ x$ on the right is $ x^{Nm}$ and it is uniquely obtained by raising $ c_N x^N$ to the $ m$th power, so we have $ M = Nm$ $ d_M = a_mc_N^m$. How can we get $ x^{M-1} = x^{Nm-1}$? One way is to raise $ c_Nx^N$ to the $ (m-1)$st power and multiply by $ c_{N-1}x^{N-1}$, which appears in the multinomial with coefficient $ m$. We claim that this is the only contribution to $ d_{M-1}$. Indeed, raising $ x^{N-1}$ to the $ m$th power yields $ x^{Nm-m}$ and since $ m>1$ this is not $ x^{M-1}$. This is where the assumption "degree at least $ 2$" of $ f$ comes in. It's not hard to see that other combinations in the multinomial aren't going to yield $ x^{Nm-1}$ either. Also, the second term (the one following $ a_{m-1}$) has degree $ Nm-N < Nm-1$ since $ N>1$ follows from $ m>1$. Therefore, $ d_{M-1} = ma_mc_N^{m-1}c_{N-1}$. We can now compare the average $ r_n$ of $ g_n$'s roots with that of $ g_{n+1}$. We have: $ r_n = - \frac{c_{N-1}}{N c_N}$ $ r_{n+1} = -\frac{d_{M-1}}{M d_M} = -\frac{m a_m c_N^{m-1}c_{N-1}}{Nm a_m c_N^m}$ and these two are obviously equal. Since this holds for an arbitrary $ n$, the average $ r_n$ remains constant. QED