Closed form for $\sum\limits_{k=0}^{b}k^na^k$

Question

We can be sure that for $a>1$ $$\sum\limits_{k=1}^{\infty}(-k)^na^{-k}+\sum\limits_{k=0}^{b}k^na^k=a^b\sum\limits_{m=0}^{n}\binom{n}{m}b^{n-m}\sum\limits_{k=0}^{\infty}(-k)^ma^{-k}$$ where $$\sum\limits_{k=0}^{\infty}k^na^{-k}=\frac{af(a,n)}{(a-1)^{n+1}}$$ $$f(a,n)=\sum\limits_{k=0}^{n}k!{n\brace k}(a-1)^{n-k}=\sum\limits_{k=0}^{n}\sum\limits_{j=0}^{k}\binom{k}{j}(a-1)^{n-k}j^{n}(-1)^{k-j}$$ $$\lim\limits_{n\to \infty}\frac{f(a,n+1)}{f(a,n)}-\frac{f(a,n)}{f(a,n-1)}=\frac{a-1}{\ln(a)}$$ so $$\sum\limits_{k=1}^{n}\sum\limits_{j=1}^{k}\binom{k}{j}\frac{aj^n}{(a-1)^{k+1}}(-1)^{n+k-j}+\sum\limits_{k=0}^{b}k^na^k=\sum\limits_{m=0}^{n}\sum\limits_{k=0}^{m}\sum\limits_{j=0}^{k}\binom{n}{m}\binom{k}{j}\frac{a^{b+1}j^mb^{n-m}}{(a-1)^{m+1}}(-1)^{m+k-j}$$ Very nice technique for solving this problem we can find here, but result formulas a bit ugly.

Is there more simple closed form for this sum, which involving, for example, Bernoulli numbers?

Answer 1

This has an answer using Mellin transform methods. We use the material from this MSE link which is so very similar that we may use it as a template, making adjustments as necessary.

Re-write your sum like this (here we have $a\gt 1$):

$$S_m(n) = \sum_{k=1}^n k^m a^k = n^m \sum_{k=1}^n \left(\frac{k}{n}\right)^m a^k \\ = n^m a^n + n^m \sum_{k=1}^{n-1} \left(\frac{k}{n}\right)^m a^k = n^m a^n + n^m a^n \sum_{k=1}^{n-1} \left(1 - \frac{k}{n}\right)^m a^{-k}.$$

Now consider the harmonic sum $$S(x) = \sum_{k\ge 1} a^{-k} H_m(kx)$$

where $H_m(x)$ is the Heaviside step function defined by $$H_0(x) = \begin{cases} & 1&\text{if}\quad x\in[0,1] \\ & 0 &\text{otherwise}\end{cases} \quad\text{and}\quad H_m(x) = (1-x)^m H_0(x) \quad\text{when}\quad m\in\mathbb{Z}^+.$$

We see that $$S(1/n) = \sum_{k=1}^n a^{-k} \left(1 - \frac{k}{n}\right)^m,$$ i.e. the sum that remains to be computed.

But $S(x)$ is harmonic and may be evaluated by inverting its Mellin transform.

Recall the harmonic sum identity $$\mathfrak{M}\left(\sum_{k\ge 1} \lambda_k g(\mu_k x);s\right) = \left(\sum_{k\ge 1} \frac{\lambda_k}{\mu_k^s} \right) g^*(s)$$ where $g^*(s)$ is the Mellin transform of $g(x).$

In the present case we have $$\lambda_k = a^{-k}, \quad \mu_k = k \quad \text{and} \quad g(x) = H_m(x).$$

We need the Mellin transform $H_m^*(s)$ of $H_m(x)$ which is $$\int_0^\infty H_m(x) x^{s-1} dx = \frac{m!}{s(s+1)(s+2)\cdots(s+m)}$$ as is easily seen by induction using integration by parts.

It follows that the Mellin transform $Q(s)$ of $S(x)$ is given by $$ Q(s) = \frac{m!}{s(s+1)(s+2)\cdots(s+m)} \mathrm{Li}_s(1/a) \quad\text{because}\quad \sum_{k\ge 1} \frac{\lambda_k}{\mu_k^s} = \mathrm{Li}_s(1/a).$$

We thus obtain the Mellin inversion integral $$ S(x) = \frac{1}{2\pi i} \int_{1/2-i\infty}^{1/2+i\infty} Q(s)/x^s ds$$ which we evaluate by shifting it to the left for an expansion about zero. The fundamental strip here is $\langle 0,+\infty \rangle$ which is determined by the Heaviside step function term (the polylog converges everywhere).

For the pole at $s=0$ we get $$\mathrm{Res}(Q(s)/x^s; s=0) = \frac{m!}{m!} \mathrm{Li}_{0}(1/a) = \frac{1}{a-1}.$$

For the poles at $s=-1, -2, \ldots -m = -q$ we require

$$\mathrm{Li}_{-q}(z) = \frac{1}{(1-z)^{q+1}} \sum_{p=0}^{q-1} \left\langle {q\atop p} \right\rangle z^{q-p}.$$

Observe that all terms in the sum for $\mathrm{Li}_{-q}(1/a)$ are positive (cite e.g. the combinatorial definition of the Eulerian numbers) and hence none of the poles from the Heaviside term are canceled. We may thus continue with

$$\mathrm{Res}(Q(s)/x^s; s=-q) \\ = \left.\frac{m!}{s(s+1)\cdots(s+q-1)(s+q+1)\cdots(s+m)} \frac{\mathrm{Li}_{s}(1/a)}{x^s}\right|_{s=-q} \\= \frac{m!}{(-1)^q q!\times (m-q)!} x^q \frac{1}{(1-1/a)^{q+1}} \sum_{p=0}^{q-1} \left\langle {q\atop p} \right\rangle (1/a)^{q-p} \\ = (-1)^{q} {m\choose q} x^q \frac{1}{(a-1)^{q+1}} \sum_{p=0}^{q-1} \left\langle {q\atop p} \right\rangle a^{p+1}.$$

Now returning to the sum and using $S(1/n)$ we finally have

$$S_m(n) = n^m a^n + n^m a^n \left(\frac{1}{a-1} + \sum_{q=1}^m (-1)^{q} {m\choose q} n^{-q} \frac{1}{(a-1)^{q+1}} \sum_{p=0}^{q-1} \left\langle {q\atop p} \right\rangle a^{p+1}\right).$$

This is

$$n^m \frac{a^{n+1}}{a-1} - \sum_{q=1}^m n^{m-q} {m\choose q} \frac{1}{(1-a)^{q+1}} \sum_{p=0}^{q-1} \left\langle {q\atop p} \right\rangle a^{n+p+1}.$$

We discover upon verification of this formula that it is missing a constant term that does not depend on $n,$ which indicates that the remainder integral does not vanish. To compute the constant we require

$$\sum_{q=1}^m {m\choose q} \frac{1}{(1-a)^{q}} \sum_{p=0}^{q-1} \left\langle {q\atop p} \right\rangle a^{p} \\ = \frac{1}{(1-a)^m} \sum_{q=1}^m {m\choose q} (1-a)^{m-q} \sum_{p=0}^{q} \left\langle {q\atop p} \right\rangle a^{p}.$$

What we have here is a convolution of two EGFS that yield

$$m! (1-a)^{-m} [z^m] \exp((1-a)z) \left(-1 + \frac{a-1}{a-\exp((a-1)z)}\right) \\ = m! [z^m] \exp(z) \left(-1 + \frac{a-1}{a-\exp(-z)}\right) = m! [z^m] \frac{1-\exp(z)}{a-\exp(-z)}.$$

Collecting everything we find

$$\frac{a^2}{1-a} + a + \frac{a^2}{1-a} m! [z^m] \frac{1-\exp(z)}{a-\exp(-z)} \\ = \frac{a^2}{1-a} \left(1 + \frac{1-a}{a} + m! [z^m] \frac{1-\exp(z)}{a-\exp(-z)} \right) \\ = \frac{a^2}{1-a} m! [z^m] \left(\frac{1}{a} \exp(z) + \frac{1-\exp(z)}{a-\exp(-z)} \right) \\ = \frac{a^2}{1-a} m! [z^m] \frac{-1/a + 1}{a-\exp(-z)} = \frac{a}{1-a} m! [z^m] \frac{a-1}{a-\exp(-z)} \\ = \frac{a}{(1-a)^{m+1}} m! [z^m] \frac{a-1}{a-\exp((a-1)z)} = \frac{a}{(1-a)^{m+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle a^{p}.$$

We have established the following conjecture for $S_m(n):$

$$\bbox[5px,border:2px solid #00A000]{ \color{blue}{n}^m \frac{a^{n+1}}{a-1} - \sum_{q=1}^m \color{blue}{n}^{m-q} {m\choose q} \frac{1}{(1-a)^{q+1}} \sum_{p=0}^{q-1} \left\langle {q\atop p} \right\rangle a^{n+p+1} + \frac{a}{(1-a)^{m+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle a^{p}.}$$

This is a finite expansion in $n$ and $a$ with $m+2$ terms. E.g. we obtain for $m=5$ and $a=11:$

$${\frac {11\,{n}^{5}{11}^{n}}{10}}-{\frac {11\,{n}^{4}{11}^{n}}{20}} +{\frac {33\,{n}^{3}{11}^{n}}{25}}-{\frac {913\,{n}^{2}{11}^{n}}{500}} +{\frac {957\,n{11}^{n}}{625}}-{\frac {7909\,{11}^{n}}{12500}} +{\frac {7909}{12500}}.$$

Addendum. We also have from first principles that

$$S_m(n) = [z^n] \frac{1}{1-z} \mathrm{Li}_{-m}(az) = [z^n] \frac{1}{1-z} \frac{1}{(1-az)^{m+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle a^{m-p} z^{m-p}.$$

This is

$$(-1)^m \mathrm{Res}_{z=0} \frac{1}{z^{n+1}} \frac{1}{z-1} \frac{1}{(z-1/a)^{m+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle \frac{1}{a^{p+1}} z^{m-p}.$$

Residues sum to zero and the residue at infinity is zero by inspection. We get from the residue at $z=1$ (flip sign)

$$(-1)^{m+1} \frac{1}{(1-1/a)^{m+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle \frac{1}{a^{p+1}} = (-1)^{m+1} \frac{a}{(a-1)^{m+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle a^{m-1-p} \\ = \frac{a}{(1-a)^{m+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle a^p.$$

For the residue at $z=1/a$ we write (flip sign)

$$(-1)^{m+1} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle \frac{1}{a^{p+1}} \mathrm{Res}_{z=0} \frac{1}{z-1} \frac{1}{(z-1/a)^{m+1}} z^{m-p-n-1}.$$

We require the derivative

$$\frac{1}{m!} \left(\frac{1}{z-1} z^{m-p-n-1}\right)^{(m)} \\ = \frac{1}{m!} \sum_{q=0}^m {m\choose q} \frac{(-1)^q q!}{(z-1)^{q+1}} (m-p-n-1)^{\underline{m-q}} z^{m-p-n-1-(m-q)} \\ = \sum_{q=0}^m \frac{(-1)^q}{(z-1)^{q+1}} {m-p-n-1\choose m-q} z^{q-p-n-1}.$$

Evaluate at $z=1/a$ to get

$$(-1)^{m+1} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle \frac{1}{a^{p+1}} \sum_{q=0}^m \frac{(-1)^q}{(1/a-1)^{q+1}} {m-p-n-1\choose m-q} \frac{1}{a^{q-p-n-1}} \\ = (-1)^{m+1} a^{n+1} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle \sum_{q=0}^m \frac{(-1)^q}{(1-a)^{q+1}} {m-p-n-1\choose m-q}.$$

With some algebra we have obtained the alternate closed form

$$\bbox[5px,border:2px solid #00A000]{ (-1)^{m+1} a^{n+1} \sum_{q=0}^m \frac{(-1)^q}{(1-a)^{q+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle {p-n\choose m-q} + \frac{a}{(1-a)^{m+1}} \sum_{p=0}^{m-1} \left\langle {m\atop p} \right\rangle a^{p}.}$$

Note that the binomial coefficient will produce polynomials in $n$ of degree $m-q$ when we fix $m.$

Answer 2

If you enjoy special functions $$S_b=\sum\limits_{k=0}^{b}k^na^k=\text{Li}_{-n}(a)-a^{b+1}\, \Phi (a,-n,b+1)$$ where appear the polylogarithm and Lerch transcendent functions. $$T=\sum\limits_{k=0}^{\infty}k^na^k=\Phi (a,-n,0)$$ where appears the Hurwitz-Lerch transcendent function.