Power series whose coefficients are powers of the natural numbers

以自然数幂为系数的幂级数 苏剑林 · 2010-10-16 · Mathematics series natural number power generating function

$\sum_{i=0}^{\infty} a_i x^i=a_0+a_1 x+a_2 x^2+a_3 x^3+...$

Recently, while preparing for a math competition, I've been looking into problems involving sequences and combinatorics. Since I dislike inventing a bespoke trick for every single problem, I much prefer general-purpose methods, even if they make the process a bit more cumbersome. That's why I have a soft spot for mathematical induction (recursion) and the generating function method. The former only requires writing down the recursive relation of the problem, without needing to analyze it in detail — in the end it just reduces the problem to solving a functional equation. The latter cleverly sets up a one-to-one correspondence between a sequence ${a_n}$ and a power series $\sum_{i=0}^{\infty} a_i x^i$, and then obtains the result through algebraic manipulation or calculus. Here we don't need to worry about the convergence of the series; we only need to know which "generating function" it corresponds to (expanding the generating function as a Taylor series gives back the series $\sum_{i=0}^{\infty} a_i x^i$). Clearly, both of these methods ultimately reduce the problem to an algebraic one. more

The generating function method was first applied to probability by Laplace, and was later generalized into a widely used technique. Because it relies on algebraic manipulation, it extends very well to other settings. In the future I'll spend some time discussing applications of the generating function method with you, but here let's first look at one particular question: the generating function method generally corresponds to an infinite series, so given the general term formula for $a_n$, can we work out the function that $\sum_{i=0}^{\infty} a_i x^i$ corresponds to? What we want to study below is $\sum_{n=1}^\infty n^m x^n,m\in N_+$, where m is a constant. That is, $1^m x+2^m x^2+3^m x^3+...$.

From calculus, we already know that

$$\sum_{n=1}^\infty n^0 x^n=x+x^2+x^3+...=\frac{1}{1-x}-1$$

and also that

$$\sum_{n=1}^\infty n^m x^n=x\sum_{n=1}^\infty n^m x^{n-1}=x\sum_{n=1}^\infty \frac{d(n^{m-1} x^n)}{dx}=x\frac{\sum_{n=1}^\infty n^{m-1} x^n}{dx}$$

Through this transformation, we've "reduced the degree" of the problem's $n^m$ down to $n^{m-1}$. Following this idea, we can derive a recursive formula. Let $T_m=\sum_{n=1}^\infty n^m x^n$, then

$$T_1=\frac{x}{1-x}$$

$T_{m+1}=x\frac{dT_m}{dx}$