The generating function of $s_j(n)=\sum_{k=0}^{n}k^j$ and a polynomial in $1/(1-x)$

Question

I recently found the generating function for the sequence $$s_j(n)=\sum_{k=0}^{n}k^j,$$ where $j\ge0$ is an integer. That is, I found an explicit formula for the function $$f_j(x)=\sum_{n\ge0}s_j(n+1)x^n.$$ Here is my derivation. Notice that $$s_j(n+2)=(n+2)^j+s_j(n+1)$$ so that $$s_j(n+2)x^{n+1}=(n+2)^jx^{n+1}+s_j(n+1)x^{n+1}$$ and hence $$\sum_{n\ge0}s_j(n+2)x^{n+1}=x\sum_{n\ge0}s_j(n+1)x^n+\sum_{n\ge0}(n+2)^jx^{n+1}.$$ This is equivalent to $$f_j(x)=\frac{1+m_j(x)}{1-x},$$ where $$m_j(x)=\sum_{n\ge1}(n+1)^jx^n=D^j\frac{x}{1-x},$$ in which we have used the operator $$D:f(x)\mapsto f(x)+xf'(x)=\frac{d}{dx}xf(x).$$ I've manually calculated the first few $m_j(x)$ functions: $$m_0(x)=\sum_{n\ge1}x^n=\frac{x}{1-x}$$ $$m_1(x)=\frac{d}{dx}\frac{x^2}{1-x}=u^2-1,$$ $$m_2(x)=D m_1(x)=-u^2+2u^3-1,$$ $$m_3(x)=D m_2(x)=u^2-6u^3+6u^4-1,$$ where $u=1/(1-x)$.

I would like a little help with the following questions. For $j>0$,

• Can one prove that $m_j$ is a polynomial of degree $j+1$ in $u$?

• Assuming the answer to the first question is yes, is there a general formula for the coefficients $a_j(r)$, where $$m_j(x)=\sum_{r=0}^{j+1}a_j(r)u^r?$$

Any help is appreciated. Thanks.

Answer 1

The connection between $f_j(x)$ and $m_j(x)$ is also seen from the $\left[\sum\limits_{n=0}^{\infty}\sum\limits_{k=0}^{n}=\sum\limits_{k=0}^{\infty}\sum\limits_{n=k}^{\infty}\right]$ trick: $$\sum_{n=0}^{\infty}x^n\sum_{k=\color{red}{1}}^{n+1}k^j=\sum_{k=0}^{\infty}(k+1)^j\sum_{n=k}^{\infty}x^n=\frac{g_j(x)}{1-x},$$ where $g_j(x)=\sum\limits_{k=0}^{\infty}(k+1)^j x^k=1+m_j(x)$, and the LHS equals $f_j(x)$ when $j>0$. Now:

1. Yes, $g_j(x)$ [equivalently, $m_j(x)$] is a polynomial in $u=1/(1-x)$ of degree $j+1$; to see this, write $g_j(x)=h_j\big(1/(1-x)\big)$; then $h_0(u)=u$ and, using $g_{j+1}(x)=\big(xg_j(x)\big)'$ and the chain rule, $$h_{j+1}\Big(\frac{1}{1-x}\Big)=g_j(x)+xg_j'(x)=h_j\Big(\frac{1}{1-x}\Big)+\frac{x}{(1-x)^2}h_j'\Big(\frac{1}{1-x}\Big),$$ which transforms into $h_{j+1}(u)=h_j(u)+u(u-1)h_j'(u)$, yielding the claim by induction.
2. Yes, there is a formula. It involves Stirling numbers of the second kind. To deduce it directly, note that $$G(x,y):=\sum_{j=0}^{\infty}g_j(x)\frac{y^j}{j!}=\sum_{j,k=0}^{\infty}(k+1)^j\frac{x^k y^j}{j!}=\sum_{k=0}^{\infty}e^{(k+1)y}x^k=\frac{e^y}{1-xe^y}$$ if $y$ is small enough, so that, setting $u=1/(1-x)$ again, we get $$H(u,y):=\sum_{j=0}^{\infty}h_j(u)\frac{y^j}{j!}=\frac{u}{1-(1-e^{-y})u}.$$ Now we expand it in powers of $u$ and $y$, using $$(1-e^{-y})^r=\sum_{k=0}^{r}\binom{r}{k}(-1)^k\underbrace{\sum_{j=0}^{\infty}\frac{(-ky)^j}{j!}}_{=e^{-ky}}=\sum_{j=\color{red}{r}}^{\infty}\frac{(-y)^j}{j!}\underbrace{\sum_{k=0}^{r}\binom{r}{k}(-1)^{k}k^j}_{=(-1)^r r!\begin{Bmatrix}j\\r\end{Bmatrix}}$$ (the lower limit of $j=r$ is justified by $1-e^{-y}=y+\ldots$). Thus, $$h_j(u)=\sum_{r=0}^{j}(-1)^{j-r} r!\begin{Bmatrix}j\\r\end{Bmatrix}u^{r+1}.$$