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. $\deg P_i < \deg P_{i-2}$ and $P_i = P_{i-2} + P_{i-1}Q_i$, therefore $\deg(P_{i-1}Q_i) = n-i+2$, hence $\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 \neq 0$ and $\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 $\deg(R_{n0}) = n - 2$ and $\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 $\deg \tilde{R} \ge \deg P_1 = n - 1$. If $\tilde{R} = 0$ then $\deg R = \deg R_{n0} = n - 2$. If $\deg \tilde{R} \ge n - 1$ then $\deg R = \deg \tilde{R} \ge n - 1$. Therefore $\deg R \ge n - 2$. It can be proved in the similar manner that $\tilde{S}$ divides by $P_0$, and from this that $\deg S \ge n - 1$, which is to be proven.