Solution:
We shall prove by strong induction on $d \geq 0$ the existence of a polynomial $P_{d}(x)$ of degree $d+1$ with rational coefficients such that
- the exponents of $x$ which occur with nonzero coefficients are all of opposite parity from $d$;
- $P_{d}(2n+1) - P_{d}(2n-1) = n^{d}$ (defined to be $1$ when $n = d = 0$);
- $P_{d}(1) = 1/2$ if $d = 0$, and $P_{d}(1) = 0$ otherwise.

Then, $S(n) = P_{d}(2n+1)$ will meet our requirements (we know $S(n) = 0^{d} + \cdots + n^{d}$ by using the second property of $P_{d}$ to form a telescoping sum).

The base cases are $P_{0}(x) = x/2$, $P_{1}(x) = (x^{2} - 1)/8$. If $d > 1$, consider what happens when $(2n+1)^{d+1} - (2n-1)^{d+1}$ is expanded by the binomial theorem. The result is a polynomial in $n$, in which the powers having the same parity as $d+1$ cancel, leaving $c_{d} n^{d} + c_{d-2} n^{d-2} + \cdots + c_{2\lfloor d/2 \rfloor} n^{2\lfloor d/2 \rfloor}$ where, using the binomial theorem, $c_{k} = 2^{k+1} \binom{d+1}{k}$.

Now first suppose $d$ is odd. By the induction hypothesis, for any odd $k < d$, there exists a rational polynomial $P_{k}$ meeting the conditions above (and every exponent of $x$ is even). Then
$$P_{d}(x) = \frac{x^{d+1} - c_{d-2} P_{d-2}(x) - c_{d-4} P_{d-4}(x) - \cdots - c_{1} P_{1}(x) - 1}{c_{d}}$$
meets all the conditions.

If, instead, $d$ is even, then for any even $k < d$, there exists an odd rational polynomial $P_{k}$ meeting these conditions, and
$$P_{d}(x) = \frac{x^{d+1} - c_{d-2} P_{d-2}(x) - c_{d-4} P_{d-4}(x) - \cdots - c_{0} P_{0}(x)}{c_{d}}$$
meets our requirements—the first two are clear, and, for the third, we use our earlier computation that $c_{0} = 2$ to find
$$\frac{1^{d+1} - c_{0} P_{0}(1)}{c_{d}} = \frac{1 - 1}{c_{d}} = 0$$
as claimed. Thus $P_{d}$ exists as needed.