Let $\left \{ c_i \right \}_{i=0}^{\infty}$ be a sequence of non-negative real numbers with $c_{2017}>0$. A sequence of polynomials is defined as $$P_{-1}(x)=0 \ , \ P_0(x)=1 \ , \ P_{n+1}(x)=xP_n(x)+c_nP_{n-1}(x).$$Prove that there doesn't exist any integer $n>2017$ and some real number $c$ such that $$P_{2n}(x)=P_n(x^2+c).$$ Proposed by Navid Safaei
Problem
Source: 2017 Iran TST third exam day2 p5
Tags: Iran, Iranian TST, polynomial, algebra
28.04.2017 06:20
Here is a not so (or maybe so not) elegant solution. For ease of notation I will use $f_n (x) $ in place of $P_n(x) $. In the following solution assume $v_n (i) $ to be the coefficient of $x^i $ in $f_n (x) $. It is pretty obvious from the given recursion that $f_n (x) $ is a monic polynomial of degree $n $. Since all its coefficients are non-negative reals, it follows that $f_n (x)$ is increasing in $\mathbb {R}^+\cup\{0\} $. So here are a series of claims : $\text {CLAIM 1 :} $ $ v_n (i)>0\implies i\leq n $ and $i\equiv n\pmod 2$. $\text {PROOF :} $ The fact that $i\leq n $ directly follows from the fact that the degree of $f_n (x) $ is $n $. And as for proving that $i\equiv n\pmod 2$, it is enough to prove that $f_n (x) $ is even when $n $ is even and $f_n (x) $ is odd when $n $ is odd. We shall proceed by induction on $n $. The base cases obviously satiafy our needs. Assume the result to be true $\forall k\leq n $. We shall show that the parity of $f_{n+1}(x) $ is same as that of $f_{n-1}(x) $. By induction hypothesis, $f_n (x) $ and $f_{n-1}(x) $ are of opposite parity $\implies xf_n (x)$ and $f_{n-1}(x) $ are of the same parity, hence $f_{n+1}(x)=xf_n (x)+c_nf_{n-1}(x) $ has the same parity as $f_{n-1}(x) $. This completes the induction and proves the claim. $\text {CLAIM 2 :} $ $v_n (n-2)=\sum_{i=1}^{n-1}c_i$ $\text {PROOF :} $ The proof is by induction. Clearly the claim holds for base cases, so assume it ro be true $\forall k\leq n $. From the recursion we infer that $v_{n+1}(n-1)=v_n (n-2)+c_nv_{n-1}(n-1)=v_n (n-2)+c_n $. From the induction hypothesis $v_n(n-2)=\sum_{i=1}^{n-1}c_i \implies v_{n+1}(n-1)=\sum_{i=1}^nc_i $ which completes the induction and proves the claim. $\text {CLAIM 3:} $ $v_n(n-4)=\sum_{1\leq i <j\leq n-1}c_ic_j-\sum_{i=1}^{n-2}c_ic_{i+1} $. $\text {PROOF :} $ Again the proof is by induction. The base cases are obviously true. Let the result be true $\forall k\leq n $. Using the recursion, $v_{n+1}(n-3)=v_n (n-4)+c_nv_{n-1}(n-3)=v_n (n-4)+c_n\left (\sum_{i=1}^{n-2}c_i\right) $ using $\text {CLAIM 2} $. Now invoking the induction hypothesis, $v_{n+1}(n-3)=\sum_{1\leq i <j\leq n-1}c_ic_j-\sum_{i=1}^{n-2}c_ic_{i+1}+c_n\left (\sum_{i=1}^{n-2}c_i\right)=\sum_{1\leq i <j\leq n}c_ic_j-\sum_{i=1}^{n-1}c_ic_{i+1} $, hence we are done by induction. Now we are ready to slay the problem. Assume $\exists n\in\mathbb {N},c\in\mathbb {R} $ such that $f_{2n} (x)=f_n (x^2+c) $ Now comparing the coefficient of $x^{2n-2} $ and invoking $\text {CLAIM 2},v_{2n}(2n-2)=\sum_{i=1}^{2n-1}c_i $. On the other hand, $\text {CLAIM 1} $ shows that the coefficient of $x^{2n-2} $ in $f_n (x^2+c) $ is $\binom {n}{1}c=nc\implies c=\frac {\sum_{i=1}^{2n-1}c_i}{n} $. Now we shall compare the coefficients of $x^{2n-4} $ on both sides. Using $\text {CLAIM 3},v_{2n}(2n-4)=\sum_{1\leq i <j\leq 2n-1}c_ic_j-\sum_{i=1}^{2n-2}c_ic _{i+1}$. Using $\text {CLAIM 2}$, the coefficient of $x^{2n-4} $ in $f _n (x^2+c) $ turns out to be $\binom {n}{2}c^2+\sum_{i=1}^{n-1}c_i \geq \binom {n}{2}c^2=\left (\frac {n-1}{2n}\right)\left (\sum_{i=1}^{2n-1}c_i\right)^2$ using $c=\frac {\sum_{i=1}^{2n-1}c_i}{n} $ with equality if and only if $c_i=0\forall 1\leq i< n$. But on the other hand $\left (\frac {n-1}{2n}\right)\left (\sum_{i=1}^{2n-1}c_i\right)^2\geq \sum_{1\leq i <j\leq 2n-1}c_ic_j-\sum_{i=1}^{2n-2}c_ic _{i+1}=v_{2n}(2n-4) $. Since equality actually holds we conclude that $c_i=0\forall 1\leq i<n $. But $c_{2017}>0\implies n\leq 2017$. Hence there does not exist any integer $n>2017$ such that $f_{2n}(x)=f_n (x^2+c) $ for any constant $c\in\mathbb {R}$, as required.
19.04.2020 17:05
Here is my another solution. Let’s say $v_{n}(i)$ is the coefficient of $x^{i}$ in $P_{n}(x)$. $v_{n+1}(i)=v_{n}(i-1)+c_{n}v_{n-1}(i)$ because of $P_{n+1}(x)=xP_{n}(x)+c_{n}P_{n-1}(x)$. step 1) $P_{n}(x)$’s degree is $n$ and $P_{n}(x)$ is monic.
step 2) $v_n (n-2)=\sum_{i=1}^{n-1}c_i$
step 3) $v_{2n} (0)=\prod_{i=1}^{n}c_{2i-1}$
step 4) $c$ should be $\frac{\sum_{i=1}^{2n-1}c_{i}}{n}$.
step 5) Let’s assume that $P_{2n}(x)=P_{n}(x^{2}+c)$. For all $x>0$, $P_{n}(x)>x^{n}$ because $P_{n}(x)$’s all coefficient is not negative and $c_{2017}>0$. $P_{2n}(0)=\prod_{i=1}^{n}c_{2i-1}\le(\frac{\sum_{i=1}^{n}c_{2i-1}}{n})^{n}\le (\frac{\sum_{i=1}^{2n-1}c_{i}}{n})^{n}=c^{n}<P_{n}(c)$, so it is a contradition.
02.08.2020 22:55
For convenience, write $:=$ $$ S_k = \sum_{i=1}^{k} c_i \qquad \text{and} \quad R_k = \sum_{i=1}^{k} S_i \cdot c_{i+2}$$ $$\textbf {Part one : The coefficients}$$ It is easily observed by induction that $$P_n(x)= x^n + S_{n-1}\cdot x^{n-2} + R_{n-3} \cdot x^{n-4} + \dots$$The details are quite straightforward, so I wont bother writing them down . Claim $:=$ $R_{n-3}= \sum_{1\leq i < j \leq n-1} c_ic_j - \sum_{i=1}^{n-2} c_ic_{i+1}$ Proof : Its just a matter of manipulating some double sums. Write $:=$ $$R_{n-3} = \sum_{i=1}^{n-3} S_i \cdot c_{i+2}= \sum_{i=1}^{n-3} \sum_{j=1}^{i}c_j \cdot c_{i+2}$$$$ \implies R_{n-3} = \sum_{j=1}^{n-3} c_j \cdot \left(\sum_{i=j+2}^{n-1} c_i \right)= \sum_{j=1}^{n-3} c_j \cdot (c_{j+2}+c_{j+3}+ \dots +c_{n-1})$$$$\implies \boxed {R_{n-3}= \sum_{1\leq i < j \leq n-1} c_ic_j - \sum_{i=1}^{n-2} c_ic_{i+1}}$$ Next , FTSOC the problem statement is false, then there exists a positive integer $n >2017$ and a real $c$ such that $$P_{2n}(x)=P_{n}(x^2+c)$$ Comparing the coefficients of $x^{2n-2}$ and $x^{2n-4}$ we have $:=$ $$ \binom n1 \cdot c = S_{2n-1}$$$$ \binom n2 \cdot c^2 + S_{n-1} = R_{2n-3}= \sum_{1\leq i < j \leq 2n-1} c_ic_j - \sum_{i=1}^{2n-2} c_ic_{i+1}$$ Substituting the value of $c$ from the first equation we have $:=$ $$S_{n-1} + \frac {n(n-1)}2 \cdot \frac {(S_{2n-1})^2}{n^2} = \frac 12 \left((S_{2n-1})^2-\sum_{i=1}^{2n-1}c_i^2 \right) - \sum_{i=1}^{2n-2}c_ic_{i+1}$$$$\implies \frac 1n (S_{2n-1})^2 = \sum_{k=1}^{2n-1}c_k^2 + 2 \sum_{k=1}^{2n-2}c_kc_{k+1} +2\sum_{k=1}^{n-1}c_k$$$$\implies \boxed{ \frac 1n \left(\sum_{k=1}^{2n-1}c_k \right)^2 =\sum_{k=1}^{2n-1}c_k^2 + 2 \sum_{k=1}^{2n-2}c_kc_{k+1} +2\sum_{k=1}^{n-1}c_k}$$ Call the above equation as $\spadesuit.$ $$\textbf {Part two : Bounding}$$ We claim that equality in $\spadesuit$ cannot hold. We will use the following estimates $:=$ $$\frac 1n \left(\sum_{k=1}^{2n-1}c_k \right)^2 \stackrel {\text{C-S}}{\leq} c_1^2 + \sum_{k=1}^{n-1} (c_{2k}+ c_{2k+1})^2$$$$\frac 1n \left(\sum_{k=1}^{2n-1}c_k \right)^2 \stackrel {\text{C-S}}{\leq} c_{2n-1}^2 + \sum_{k=1}^{n-1} (c_{2k}+ c_{2k-1})^2$$$$\implies \frac 2n \left(\sum_{k=1}^{2n-1}c_k \right)^2 \leq 2\sum_{k=1}^{2n-1} c_{k}^2 +2 \sum_{k=1}^{2n-2}c_kc_{k+1}$$ However invoking $\spadesuit$ , we get $:=$ $$ \sum_{k=1}^{2n-2}c_kc_{k+1} +2\sum_{k=1}^{n-1} c_k \leq 0$$ However since we have that $c_k \geq 0$ and $c_{2017}>0$ , hence the above inequality can never hold . Hence we come to the desired contradiction . The end $\blacksquare$
07.10.2020 19:32
Solved with nukelauncher. First, we can actually explicitly describe all \(P\): Claim: If the summation below sums over all subsets \(S\subseteq[n-1]\) with no two consecutive elements, then \[P_n(x)=\sum_S\left(x^{n-2|S|}\cdot\prod_{x\in S}c_s\right).\] Proof. Easy induction. \(\blacksquare\) Let \(P_{2n}(x)\equiv P_n(x^2+c)\) hold for some \(n\); we will show \(n\le2017\). Notation-wise, let \(a_k(P)\) denote the coefficient of \(x^k\) in \(P\). Then \[a_{2n-2}\left(P_n(x^2+c)\right)=a_{2n-2}\left( (x^2+c)^n\right)=nc.\]Setting this equal to \(a_{2n-2}\left(P_{2n}(x)\right)\), we have \(c=\frac{c_1+\cdots+c_{2n-1}}n\). Next, observe that \[a_{2n-4}\left(P_{2n}(x)\right)=\sum_{i=1}^{2n-3}\sum_{j=i+2}^{2n-1}c_ic_j=\frac{(c_1+\cdots+c_{2n-1})^2+\sum_{i=1}^{2n-1}c_i^2}2-\sum_{i=1}^{2n-2}c_ic_{i+1},\]which is equal to \begin{align*} a_{2n-4}\left(P_n(x^2+c)\right)&=a_{2n-4}\left( (x^2+c)^n+(c_1+\cdots+c_{n-1})(x^2+c)^{n-2}\right)\\ &=\binom n2\cdot c^2+(c_1+\cdots+c_{n-1})\\ &=\frac{n(n-1)}2\frac{(c_1+\cdots+c_{2n-1})^2}{n^2}+(c_1+\cdots+c_{n-1})\\ &=\frac{(c_1+\cdots+c_{2n-1})^2}2-\frac12\frac{(c_1+\cdots+c_{2n-1})^2}n+(c_1+\cdots+c_{n-1}). \end{align*}Setting this equal to \(a_{2n-4}(P_{2n}(x))\), we obtain the identity \[\frac{(c_1+\cdots+c_{2n-1})^2}n=2(c_1+\cdots+_{n-1})+\sum_{i=1}^{2n-1}c_i^2+2\sum_{i=1}^{2n-2}c_ic_{i+1}.\] However, notice that \[\frac{(c_1+\cdots+c_{2n-1})^2}n\le(c_1+c_2)^2+(c_3+c_4)^2+\cdots+c_{2n-1}^2\le\sum_{i=1}^{2n-1}c_i^2+2\sum_{\substack{i=1\\ i\text{ odd}}}^{2n-2}c_ic_{i+1},\]so we must have \(2(c_1+\cdots+c_{n-1})=0\), i.e.\ \(c_1=c_2=\cdots=c_{n-1}=0\). Since \(c_{2017}\ne0\), we must have \(n\le2017\), as claimed.
24.06.2022 11:14
It is easy to prove via induction that for all positive integers $t$, $$[x^{t-2}] P_t(x)=c_1+\cdots+c_{t-1}$$ $$[x^{t-4}] P_t(x)=\sum\limits_{1\le i<j\le t-1, j\ne i+1} c_ic_j$$ Surprisingly, inequalities about these sums should solve the problem. Suppose $P_{2n}(x)=P_n(x^2+c)$ Comparing $x^{2n-2}$-coefficients, $c=\frac{c_1+\cdots+c_{2n-1}}{n}$ Comparing $x^{2n-4}$ coefficients, $$ \sum\limits_{1\le i<j\le 2n-1, j\ne i+1} c_ic_j=\binom n2 \frac{(c_1+\cdots+c_{2n-1})^2}{n^2} + (c_1+\cdots+c_{t-1})$$ I claim $$\sum\limits_{1\le i<j\le 2n-1, j\ne i+1} c_ic_j\le \binom n2 \frac{(c_1+\cdots+c_{2n-1})^2}{n^2}$$which solves the problem. Rearranging, this is equivalent to $$\frac 12 ((c_1+\cdots+c_{2n-1})^2 - c_1^2-\cdots-c_{2n-1}^2 - c_1c_2-\cdots - c_{2n-2}c_{2n-1} \le (\frac 12 - \frac{1}{2n}) (c_1+\cdots+c_{2n-1})^2$$ $$\iff c_1^2+\cdots+c_{2n-1}^2+c_1c_2+\cdots+c_{2n-2}c_{2n-1} \ge \frac{1}{n} (c_1+\cdots+c_{2n-1})^2$$ Take indices mod $2n-1$, let $x_j=c_j+c_{j+1}$ Then this rearranges to $LHS\ge \frac 12 (x_1^2+\cdots+x_{2n-2}^2)+\frac 14 x_{2n-1}^2$ and $RHS=\frac{1}{4n} (x_1+\cdots+x_{2n-1})^2$ By convexity, if RHS is fixed and I move LHS, I should have $x_1=\cdots=x_{2n-2}$ since replacing $x_1,\cdots, x_{2n-2}$ with their arithmetic mean reduces LHS. Therefore, this becomes a two variable inequality. In the end if $x=x_1, z=x_{2n-1}$ then I need to show $$\left( \frac 32-\frac 1n\right) x^2 + \left( \frac 14 - \frac{1}{4n}\right) z^2\ge \frac{n-1}{n}xz$$ Which is obvious by AM-GM and $n>2017$