Given the polynomial sequence $(p_{n}(x))$ satisfying $p_{1}(x)=x^{2}-1$, $p_{2}(x)=2x(x^{2}-1)$, and $p_{n+1}(x)p_{n-1}(x)=(p_{n}(x)^{2}-(x^{2}-1)^{2}$, for $n\geq 2$, let $s_{n}$ be the sum of the absolute values of the coefficients of $p_{n}(x)$. For each $n$, find a non-negative integer $k_{n}$ such that $2^{-k_{n}}s_n$ is odd.
Problem
Source: 2002 China National Olmpiad
Tags: algebra, polynomial, algebra proposed
19.02.2018 07:32
This is my solution. Claim 1) $P_{n+1}(x)=2xP_n(x)-P_{n-1}.$ We proceed by induction. $n=2$ $P_3(x)P_1(x)=(2xP_2(x)-P_1(x))P_1(x)=(P_2(x))^2-(P_1(x))^2.$ so this works well. Assume that it is true for all values less than $n\ge3.$ Then, $P_{n+1}(x)P_{n-1}(x)=P_n(x)^2-P_1(x)^2$ $=P_n(x)(2xP_{n-1}(x)-P_{n-2}(x))-P_1(x)^2$ $=2xP_n(x)P_{n-1}(x)-(P_n(x)P_{n-2}(x)+P_1(x)^2)$ $=2xP_n(x)P_{n-1}(x)-P_{n-1}(x)^2$ Hence, $P_{n+1}(x)=2xP_n{x}-P_{n-1}(x).$ Claim 2) Each terms of $2xP_n(x)$ and $-P_{n-1}(x)$ has the same sign. Note that $P_n(x)$ is a polynomial with degree $n+1$ and if $n$ is even, it only has terms with an odd degree and otherwise, even degree. Also, coefficient of highest degree is $(+)$ and after that $(-)$ and $(+)$ alternates. If we prove this, it is sufficient to prove our second claim. $P_1(x)=x^2-1, P_2(x)=2x^3-2x$ so we are good. From, our first claim, \begin{tabular}{|c|l|l|l|l|} \hline & n+2 & n & $\cdots$ & \\ \cline{1-5} $2xP_n$ & + & - & + & $\cdots$ \\ \cline{1-5} $-P_{n-1}$ & & - & + & $\cdots$ \\ \cline{1-5} \hline \end{tabular} that in $P_{n+1}$ the degree is $n+2$ and the terms appear in only same parity of degree(i.e $n+2, n, n-2 \cdots$). Also, the signs alternate as well. Claim 3) $S_1=2, S_2=4, S_{n+1}=2S_{n}+S_{n-1}.$ This just immediately follows from our second claim. Solving the recursion, we get $S_n=\frac{1}{\sqrt{2}}[(1+\sqrt{2})^n-(1-\sqrt{2})^n]$ Now, let's forget about the polynomials and just focus on $S_n.$ Claim 4) $k_n=2L(n),$ where $L(n)=v_2(n).$ Keep in mind that our $k_n=L(S_n).$ Using Binomial Theorem, $S_n= 2^{-\frac{1}{2}}[\sum_{i=0}^n\binom{n}{i}2^{\frac{i}{2}}-\sum_{i=0}^n\binom{n}{i}(-1)^i 2^{\frac{i}{2}}]$ $=\sum_{0\le 2\nmid i\le n}\binom{n}{i}2^{\frac{i+1}{2}}$ Let $i=2r+1$ and since $\binom{n}{2r+1}=\frac{n}{2r+1}\binom{n-1}{2r},$ we have $S_n=\sum_{0\le r\le\frac{n-1}{2}}\binom{n}{2r+1}2^{r+1}=2n+\sum_{1\le r\le\frac{n-1}{2}}\binom{n-1}{2r}\cdot\frac{2^r\cdot 2n}{2r+1}.$ If $1\le r\le\frac{n-1}{2}, 2^{L(n)+1}|2^r\cdot 2n,$ that $2^{L(2n)+1}|\binom{n-1}{2r}\cdot 2^r\cdot 2n.$ However, since $2r+1$ is odd, $2^{L(n)+1}|\binom{n-1}{2r}\cdot\frac{2^r\cdot2n}{2r+1}$ for $1\le r\le\frac{n-1}{2}.$ Hence, $2^{L(2n)+1}|\sum_{1\le r\le\frac{n-1}{2}}\binom{n-1}{2r}\cdot\frac{2^r\cdot2n}{2r+1}.$ We can write $2n$ as $2n=2^{L(2n)}(2t+1)$ for some $t\in\mathbb{N}$ and $\sum_{1\le r\le\frac{n-1}{2}}\binom{n-1}{2r}\cdot\frac{2^r\cdot2n}{2r+1}$ as $\sum_{1\le r\le\frac{n-1}{2}}\binom{n-1}{2r}\cdot\frac{2^r\cdot2n}{2r+1}=2^{L(n)+1}s$ for some $s\in\mathbb{N}.$ Therefore, $S_n=2^{L(n)}(2t+1)+2^{L(2n)+1}s=2^{L(2n)}(2(t+s)+1)$ that our proof is complete. $\therefore k_n=2v_2(n).$