The Problems of Ukrainian Authors

It is possible that the degree of the sum of two polynomials is less than the degree of one summand only if their degrees equal. For shortening we pull down $(x)$ in the notation. $\mathrm{deg}{P}_i<\mathrm{deg}{P}_{i-2}$ and $P_i=P_{i-2}+P_{i-1}{Q}_i$, therefore $\mathrm{deg}(P_{i-1}{Q}_i)=n-i+2$, hence $\mathrm{deg}(Q_i)=1$ for all integer $i=2,n$.

Let's prove by induction by $i=2,n$, that there exist polynomials $R_i$ and $S_i$ of degrees $i-2$ and $i-1$ respectively, satisfying $P_i=P_0{R}_i+P_1{S}_i$.

Base. For $i=2$ we can get $R_i=1$ and $S_i=Q_2$.

Induction step. Let for all $i$, $2\le i\le k$ ($k<n$) there exist required $R_k$ and $S_k$. We will construct required polynomials for $i=k+1$. We have from the statement: $P_{k+1}=P_{k-1}+P_k{Q}_{k+1}$.

In the case $k>2$ we get from the induction assumption:

$P_{k+1}=(P_0{R}_{k-1}+P_1{S}_{k-1})+(P_0{R}_k+P_1{S}_k)Q_{k+1}=(R_{k-1}+R_k{Q}_{k+1})P_0+(S_{k-1}+S_k{Q}_{k+1})P_1$.

And we can set $R_{k+1}=R_{k-1}+R_k{Q}_{k+1}$ and $S_{k+1}=S_{k-1}+S_k{Q}_{k+1}$.

For $k=2$: $P_{k+1}=P_1+(P_0{R}_2+P_1{S}_2)Q_3=(R_2{Q}_3)P_0+(1+S_2{Q}_3)P_1$. And we can set $R_{k+1}=R_2{Q}_3$ and $S_{k+1}=1+S_2{Q}_3$. In both cases degrees of $R_{k+1}$ and $S_{k+1}$ are as required. The statement proved.

If we set $i=n$, then $P_i=P_0{R}_i+P_1{S}_i$, or, taking into account $P_i\ne 0$ and $\mathrm{deg}(P_i)=0$, for $R_{n0}=\frac{R_n}{P_n}$ and $S_{n0}=\frac{S_n}{P_n}$ it holds $P_0{R}_{n0}+P_1{S}_{n0}=1$ (and at that $\mathrm{deg}(R_{n0})=n-2$ and $\mathrm{deg}(S_{n0})=n-1$).

Let for some other $R$ and $S$ it holds $P_{0}R+P_{1}S=1$. Then $P_0(R-R_{n0})+P_1(S-S_{n0})=0$, or $P_0\tilde{R}+P_1\tilde{S}=0$ for $\tilde{R}=R-R_{n0}$, $\tilde{S}=S-S_{n0}$.

Let's prove that $\tilde{R}$ divides by $P_1$, i.e. there exists polynomial $C$, for which $\tilde{R}=P_{1}C$. By multiplying both sides by $R_{n0}$, we get $P_0{R}_{n0}\tilde{R}+P_1{R}_{n0}\tilde{S}=0$. Taking into account preceding formulas: $P_0{R}_{n0}=1-P_1{S}_{n0}$. Let's substitute this equality into previous one: $(1-P_1{S}_{n0})\tilde{R}+P_1{R}_{n0}\tilde{S}=0$, whence $\tilde{R}-P_1{S}_{n0}\tilde{R}+P_1{R}_{n0}\tilde{S}=0$, or $\tilde{R}=P_1(S_{n0}\tilde{R}-R_{n0}\tilde{S})$, which is required.

And so either $\tilde{R}=0$ or $\mathrm{deg}\tilde{R}\ge \mathrm{deg}{P}_1=n-1$. If $\tilde{R}=0$ then $\mathrm{deg}R=\mathrm{deg}{R}_{n0}=n-2$. If $\mathrm{deg}\tilde{R}\ge n-1$ then $\mathrm{deg}R=\mathrm{deg}\tilde{R}\ge n-1$. Therefore $\mathrm{deg}R\ge n-2$. It can be proved in the similar manner that $\tilde{S}$ divides by $P_0$, and from this that $\mathrm{deg}S\ge n-1$, which is to be proven.