Canadian Mathematical Olympiad

Solution:
The property clearly holds whenever $p(x)$ is a constant polynomial, since we can take $q(x)=x$. Assume henceforth that $p(x)$ is nonconstant and has the stated property. Let $d$ be the degree of $p(x)$, so $p(x)$ is of the form
$$p(x)=c x^{d}+\cdots .$$
By a Lemma (which we will prove at the end), $\sum_{k=1}^{n} k^{d}$ is a polynomial in $n$ of degree $d+1$, so $p(1)+p(2)+\cdots+p(n)$ is a polynomial in $n$ of degree $d+1$. Hence, $q(n)$ is a polynomial of degree 1. Furthermore, the coefficient of $n^{d+1}$ in $\sum_{k=1}^{n} k^{d}$ is $\frac{1}{d+1}$, so the coefficient of $n$ in $q(n)$ is also $\frac{1}{d+1}$. Let $q(x)=\frac{1}{d+1}(x+r)$. We have that
$$p(1)+p(2)+p(3)+\cdots+p(n)=p(n) q(n)$$
and
$$p(1)+p(2)+p(3)+\cdots+p(n)+p(n+1)=p(n+1) q(n+1) \text{.}$$
Subtracting the first equation from the second, we get
$$p(n+1)=p(n+1) q(n+1)-p(n) q(n),$$
and hence
$$p(n) q(n)=p(n+1)[q(n+1)-1] .$$
Since this holds for all positive integers $n$, it follows that
$$p(x) q(x)=p(x+1)[q(x+1)-1]$$
for all real numbers $x$. We can then write
$$p(x) \cdot \frac{1}{d+1}(x+r)=p(x+1)\left[\frac{1}{d+1}(x+r+1)-1\right]$$
so
$$(x+r) p(x)=(x+r-d) p(x+1) .$$
Setting $x=-r$, we get
$$(-d) p(-r+1)=0$$
Hence, $-r+1$ is a root of $p(x)$. Let $p(x)=(x+r-1) p_{1}(x)$. Then
$$(x+r)(x+r-1) p_{1}(x)=(x+r-d)(x+r) p_{1}(x+1),$$
so
$$(x+r-1) p_{1}(x)=(x+r-d) p_{1}(x+1) .$$
If $d=1$, then $p_{1}(x)$ is a constant, so both sides are equal, and we can say $p(x)=c(x+r-1)$.
Otherwise, setting $x=-r+1$, we get
$$(1-d) p_{1}(-r+2)=0$$
Hence, $-r+2$ is a root of $p_{1}(x)$. Let $p_{1}(x)=(x+r-2) p_{2}(x)$. Then
$$(x-r-1)(x+r-2) p_{2}(x)=(x+r-d)(x+r-1) p_{2}(x+1),$$
so
$$(x+r-2) p_{2}(x)=(x+r-d) p_{2}(x+1) \text{.}$$
If $d=2$, then $p_{2}(x)$ is a constant, so both sides are equal, and we can say $p(x)=c(x+r-1)(x+r-2)$.
Otherwise, we can continue to substitute, giving us
$$p(x)=c(x+r-1)(x+r-2) \cdots(x+r-d) .$$
Conversely, if $p(x)$ is of this form, then
$$\begin{aligned} p(x)= & c(x+r-1)(x+r-2) \cdots(x+r-d) \\ = & \frac{c(d+1)(x+r-1)(x+r-2) \cdots(x+r-d)}{d+1} \\ = & \frac{c[(x+r)-(x+r-d-1)](x+r-1)(x+r-2) \cdots(x+r-d)}{d+1} \\ = & \frac{c(x+r)(x+r-1)(x+r-2) \cdots(x+r-d)}{d+1} \\ & -\frac{c(x+r-1)(x+r-2) \cdots(x+r-d)(x+r-d-1)}{d+1} . \end{aligned}$$
Then the sum $p(1)+p(2)+p(3)+\cdots+p(n)$ telescopes, and we are left with
$$\begin{aligned} p(1)+p(2)+p(3)+\cdots+p(n)= & \frac{c(n+r)(n+r-1)(n+r-2) \cdots(n+r-d)}{d+1} \\ & -\frac{c(r)(r-1) \cdots(r-d+1)(r-d)}{d+1} . \end{aligned}$$
We want this to be of the form
$$p(n) q(n)=c(n+r-1)(n+r-2) \cdots(n+r-d) q(n)$$
for some polynomial $q(n)$. The only way that this can hold for each positive integer $n$ is if the term
$$\frac{c(r)(r-1) \cdots(r-d+1)(r-d)}{d+1}$$
is equal to 0 . This means $r$ has to be one of the values $0,1,2, \ldots, d$. Therefore, the polynomials we seek are of the form
$$p(x)=c(x+r-1)(x+r-2) \cdots(x+r-d)$$
where $r \in\{0,1,2, \ldots, d\}$.

Lemma. For a positive integer $d$,
$$\sum_{k=1}^{n} k^{d}$$
is a polynomial in $n$ of degree $d+1$. Furthermore, the coefficient of $n^{d+1}$ is $\frac{1}{d+1}$.

Proof. We prove the result by strong induction. For $d=1$,
$$\sum_{k=1}^{n} k=\frac{1}{2} n^{2}+\frac{1}{2} n$$
so the result holds. Assume that the result holds for $d=1,2,3, \ldots, m$, for some positive integer $m$. By the Binomial Theorem,
$$(k+1)^{m+2}-k^{m+2}=(m+2) k^{m+1}+c_{m} k^{m}+c_{m-1} k^{m-1}+\cdots+c_{1} k+c_{0},$$
for some coefficients $c_{m}, c_{m-1}, \ldots, c_{1}, c_{0}$. Summing over $1 \leq k \leq n$, we get
$$(n+1)^{m+2}-1=(m+2) \sum_{k=1}^{n} k^{m+1}+c_{m} \sum_{k=1}^{n} k^{m}+\cdots+c_{1} \sum_{k=1}^{n} k+c_{0} n .$$
Then
$$\sum_{k=1}^{n} k^{m+1}=\frac{(n+1)^{m+2}-c_{m} \sum_{k=1}^{n} k^{m}-\cdots-c_{1} \sum_{k=1}^{n} k-c_{0} n-1}{m+2} .$$
By the induction hypothesis, the sums $\sum_{k=1}^{n} k^{m}, \ldots, \sum_{k=1}^{n} k$ are all polynomials in $n$ of degree less than $m+2$. Hence, the above expression is a polynomial in $n$ of degree $m+2$, and the coefficient of $n^{m+2}$ is $\frac{1}{m+2}$. Thus, the result holds for $d=m+1$, which completes the induction step.