Chidzalo's Sequence One day I observed that if $ \displaystyle f(x)= \sum _{i=0} ^{n} k _{i} x ^{i}$ is divided by the linear polynomial $ px-q $ where $p$ and $ q $ are constants, then the quotient is $\displaystyle Q(x)= \sum _{i=0} ^{n-1} c _{i} x ^{i}  $, where the sequence $ \lbrace  c_{i}\rbrace _{i=0} ^{n-1}$ is inductively defined as  follows $$ c_{n-1} = \frac{k_{n}}{p} $$ and $ c_{n-1-i} = \frac{1}{p}(q c_{n-i}+k_{n-i})$     where $ i=1,2,3,...,n-1 .$ I have used this method to factorize polynomials faster in my head and have also given this to people I can trust to prove it but have failed. What I want is the non-derivation proof of this Idea. I mean that I don't want a derivation, because I did that. How can this be proved?
 A: Let's consider the equation $Q(x)(px-q)=f(x)$, that is
$$
(c_0+c_1x+\ldots+c_{n-2}x^{n-2}+c_{n-1}x^{n-1})(px-q)=k_0+k_1x+\ldots+k_{n-1}x^{n-1}+k_nx^n.
$$ 
We can multiply the polynomials on the LHS and compare the coefficient for $x^k$ with the corresponding coefficient for $x^k$ on the RHS. We start with the largest degree $x^n$:
\begin{align}
x^n&\colon \quad c_{n-1}p=k_n\quad\Leftrightarrow\quad c_{n-1}=\frac{k_n}{p},\\
x^{n-1}&\colon\quad  c_{n-2}p-c_{n-1}q=k_{n-1}\quad\Leftrightarrow\quad
c_{n-2}=\frac{c_{n-1}q+k_{n-1}}{p},\\
&\qquad\vdots\\
x^1&\colon\quad c_0p-c_1q=k_1\quad\Leftrightarrow\quad c_0=\frac{c_1q+k_1}{p}.
\end{align}
So far, so good. We have managed to get all your recursive conditions and calculated all the coefficients $c_k$ for $Q(x)$. However, one minor concern has left - we haven't looked at the last coefficient for $x^0$. If we do then
$$
x^0\colon\quad -c_0q=k_0.
$$
But we have no freedom left to satisfy this one, because $c_0$ is already calculated one step earlier, and we cannot change it now.

Conclusion: The recursion you have obtained is correct, but to get the factorization without a (constant) rest you need to know that $px-q$ is indeed a factor in $f(x)$, i.e. if $f(q/p)=0$. Then the last condition is satisfied too.

P.S. The recursion is exactly the steps in Euclidean division of polynomials.
P.P.S. You can take $p=1$, it does not affect the factorization.
