Lesson 4

This approach can be generalized to other power sums. For \(k \ge 1\), let \[S_{k}(n)=1^{k}+2^{k}+\dotsb+n^{k}\] and set \(S_{k}(0)=0\). The operator \(x\frac{d}{dx}\) multiplies the coefficient at \(x^{n}\) by \(n\): \[x\frac{d}{dx}\sum_{n=0}^{\infty}a_{n}x^{n}=\sum_{n=0}^{\infty}na_{n}x^{n}.\] Hence, \[\sum_{n=0}^{\infty}n^{k}x^{n}= \left(x\frac{d}{dx}\right)^{k}\frac{1}{1-x}.\] Taking partial sums means multiplying by \(\frac{1}{1-x}\), so \[\sum_{n=0}^{\infty}S_{k}(n)x^{n}= \frac{1}{1-x}\left(x\frac{d}{dx}\right)^{k}\frac{1}{1-x}.\] Let us explain what kind of rational function this is. If \[\mathcal{A}(x)=\frac{P(x)}{(1-x)^m},\] then \[x\mathcal{A}'(x)= \frac{x\left(P'(x)(1-x)+mP(x)\right)}{(1-x)^{m+1}}.\] Thus, each application of the operator \(x\frac{d}{dx}\) increases the power of \((1-x)\) in the denominator by at most one. Moreover, if \(\deg P \le m-1\), then the numerator after differentiation has degree at most \(m\). Starting from \(\frac{1}{1-x}\) and applying this operator \(k\) times, we get a rational function with denominator \((1-x)^{k+1}\) and numerator degree at most \(k\). Then we multiply by one more factor \(\frac{1}{1-x}\) to take partial sums. Therefore, \[\sum_{n=0}^{\infty}S_{k}(n)x^{n}= \frac{R_k(x)}{(1-x)^{k+2}}\] for some polynomial \(R_{k}(x)\) of degree at most \(k\).

Now write \[R_{k}(x)=r_{0}+r_{1}x+\dotsb+r_{k}x^{k}.\] Then the coefficient \(S_{k}(n)\) is a finite sum: \[S_{k}(n)=\sum_{j=0}^{k}r_{j}[x^{n}]\frac{x^j}{(1-x)^{k+2}}.\] For every fixed \(j\), \[[x^{n}]\frac{x^j}{(1-x)^{k+2}}=\binom{n-j+k+1}{k+1},\] which is a polynomial of degree \(k+1\). Hence \(S_{k}(n)\) is a finite sum of polynomials of degree at most \(k+1\), so \(S_{k}(n)\) itself is a polynomial in \(n\) of degree at most \(k+1\).