Representing polynomial in terms of other polynomial

Question

Does there any theorem with algorithm which says, any polynomial $P$ and $Q$ with common variable then $P$ can be represented in terms of $Q$ as $$P=\sum_{i\in S}P_iQ^i$$ and there exists unique polynomials $P_i$ have same degree for all $i$ and $S\subset\mathbb{Z}$.

For example: Sum of cube of first natural number is square of sum of first natural number that is

$P(n) = \sum_{k=1}^n k^3$ and $Q(n)= \sum_{k=1}^n k$ and $P(n)= 1\cdot Q^2(n)+0\cdot Q(n)+\ldots$

I'm not taking about polynomial division algorithm. Thanks.

Answer 1

If you specifically want that $\deg P_i < \deg Q$, the existence of such representation indeed follows from the fact that polynomials over any field form a Euclidean domain, that is, we can uniquely represent

$$ P(x) = P_0(x) + D_1(x) Q(x), $$

where $\deg P_0 < \deg Q$. Then, we can in turn represent

$$ D_1(x) = P_1(x) + D_2(x) Q(x), $$

where $\deg P_1 < \deg Q$, and so on, so you can find $P_0, P_1, \dots$ with consecutive division by $Q$ and taking remainders. Note that, generally, $\deg D_k = \deg P - k \deg Q$, so it will get down to $D_k = 0$ eventually.