# Inverse of the sum $\sum\limits_{j=1}^k (-1)^{k-j}\binom{k}{j} j^{\,k} a_j$

$k\in\mathbb{N}$

The inverse of the sum $$b_k:=\sum\limits_{j=1}^k (-1)^{k-j}\binom{k}{j} j^{\,k} a_j$$ is obviously $$a_k=\sum\limits_{j=1}^k \binom{k-1}{j-1}\frac{b_j}{k^j}$$ .

How can one proof it (in a clear manner)?

Background of the question:

It’s $$\sum\limits_{k=1}^\infty \frac{b_k}{k!}\int\limits_0^\infty \left(\frac{t}{e^t-1}\right)^k dt =\sum\limits_{k=1}^\infty \frac{a_k}{k}$$ with $\,\displaystyle b_k:=\sum\limits_{j=1}^k (-1)^{k-j}\binom{k}{j}j^{\,k}a_j$.

Note:

A special case is $\displaystyle a_k:=\frac{1}{k^n}$ with $n\in\mathbb{N}$ and therefore $\,\displaystyle b_k=\sum\limits_{j=1}^k (-1)^{k-j}\binom{k}{j}j^{\,k-n}$ (see Stirling numbers of the second kind) $$\sum\limits_{k=1}^n \frac{b_k}{k!}\int\limits_0^\infty \left(\frac{t}{e^t-1}\right)^k dt =\zeta(n+1)$$ and the invers equation can be found in A formula for $\int\limits_0^\infty (\frac{x}{e^x-1})^n dx$ .

• "obviously"?  Aug 25 '16 at 0:09
• With examples. :-) Aug 25 '16 at 7:33

Suppose we seek to show that if

$$b_n = \sum_{q=1}^n (-1)^{n-q} {n\choose q} q^n a_q$$

then

$$a_n = \sum_{q=1}^n {n-1\choose q-1} n^{-q} b_q.$$

This is

$$a_n = \sum_{q=1}^n {n-1\choose q-1} n^{-q} \sum_{p=1}^q (-1)^{q-p} {q\choose p} p^q a_p.$$

Re-indexing we find

$$\sum_{p=1}^n a_p \sum_{q=p}^n {n-1\choose q-1} n^{-q} (-1)^{q-p} {q\choose p} p^q \\ = \sum_{p=1}^n (-1)^p a_p \sum_{q=p}^n {n-1\choose q-1} (p/n)^q (-1)^q {q\choose p}.$$

The inner sum is

$$\sum_{q=p}^n \frac{q}{n} {n\choose q} (p/n)^q (-1)^q {q\choose p}.$$

Note that

$${n\choose q} {q\choose p} = \frac{n!}{(n-q)! p! (q-p)!} = {n\choose p} {n-p\choose n-q}$$

and we obtain for the sum term

$$\frac{1}{n} {n\choose p} \sum_{q=p}^n {n-p\choose n-q} \times q \times (-1)^q \times (p/n)^q \\ = \frac{1}{n} {n\choose p} \sum_{q=0}^{n-p} {n-p\choose q} \times (n-q) \times (-1)^{n-q} \times (p/n)^{n-q}.$$

We now have two cases, case A when $n\gt p$ and case B when $n=p.$ In case A we split the sum into two pieces. The first piece here is

$$\frac{1}{n} {n\choose p} \times (-1)^n (p/n)^n \times n \left(1-\frac{n}{p}\right)^{n-p}.$$

The second is

$$-\frac{1}{n} {n\choose p} \times (-1)^n (p/n)^n \times \sum_{q=1}^{n-p} {n-p-1\choose q-1} (n-p) (-1)^q (p/n)^{-q} \\ = -\frac{1}{n} {n\choose p} \times (-1)^n (p/n)^n \times (-n/p) (n-p) \left(1-\frac{n}{p}\right)^{n-p-1}.$$

$$\frac{1}{n} {n\choose p} \times (-1)^n (p/n)^n \\ \times \left( n \left(1-\frac{n}{p}\right)^{n-p} + \frac{n}{p} (n-p) \left(1-\frac{n}{p}\right)^{n-p-1}\right) \\ = \frac{1}{n} {n\choose p} \times (-1)^n (p/n)^n \\ \times \left( n \left(1-\frac{n}{p}\right)^{n-p} + n \left(\frac{n}{p} - 1\right) \left(1-\frac{n}{p}\right)^{n-p-1}\right) = 0.$$

For case $B$ when $n=p$ we do not split the sum and simply evaluate the single term that appears, which is

$$\frac{1}{n} {n\choose n} \times {0\choose 0} n (-1)^n 1^n = (-1)^n.$$

Returning to the target sum we see that we have

$$\sum_{p=1}^n (-1)^p a_p \times (-1)^p [[n=p]] = a_n$$

as claimed.

• Thank you very much for your efforts! Seems to be right but I have to check, if I understand everything. Aug 25 '16 at 7:52
• +1. The whole problem looks like a sort of 'Discrete Transform'. It has some resemblance to the Abel Integral Equation. I was trying something along those ideas but anyway I have to go for dinner. Aug 25 '16 at 23:30
• @Felix Marin : Yes, such problems are assigned to discrete mathematics. Aug 26 '16 at 7:40
• There is a similar relation in Donald Knuth et.al. $\texttt{Concrete Mathematics}$ book: Formula $\mathbf{5.48}$ in page 192. Aug 29 '16 at 4:43

In this proof, the binomial identity $$\binom{m}{n}\,\binom{n}{s}=\binom{m}{s}\,\binom{m-s}{n-s}$$ for all integers $m,n,s$ with $0\leq s\leq n\leq m$ is used frequently, without being specifically mentioned. A particular case of importance is when $s=1$, where it is given by $$n\,\binom{m}{n}=m\,\binom{m-1}{n-1}\,.$$

First, rewrite $$b_k=k\,\sum_{j=1}^{k}\,(-1)^{k-j}\,\binom{k-1}{j-1}\,j^{k-1}\,a_j\,.$$ Then, $$\sum_{k=1}^l\,\binom{l-1}{k-1}\,\frac{b_k}{l^k}=\sum_{k=1}^l\,\binom{l-1}{k-1}\,\frac{k}{l^k}\,\sum_{j=1}^k\,(-1)^{k-j}\,\binom{k-1}{j-1}\,j^{k-1}\,a_j\,.$$ Thus, \begin{align} \sum_{k=1}^l\,\binom{l-1}{k-1}\,\frac{b_k}{l^k}&=\sum_{j=1}^l\,\frac{a_j}{j}\,\sum_{k=j}^l\,(-1)^{k-j}\,\binom{l-1}{k-1}\,\binom{k-1}{j-1}\,k\left(\frac{j}{l}\right)^k \\ &=\sum_{j=1}^l\,\frac{a_j}{j}\,\binom{l-1}{j-1}\,\sum_{k=j}^l\,(-1)^{k-j}\,\binom{l-j}{k-j}\,k\left(\frac{j}{l}\right)^k\,. \end{align} Let $r:=k-j$. We have $$\sum_{k=1}^l\,\binom{l-1}{k-1}\,\frac{b_k}{l^k}=\sum_{j=1}^l\,\frac{a_j}{j}\,\binom{l-1}{j-1}\,\left(\frac{j}{l}\right)^j\,\sum_{r=0}^{l-j}\,(-1)^r\,\binom{l-j}{r}\,(r+j)\,\left(\frac{j}{l}\right)^{r}\,.\tag{*}$$

Now, if $j=l$, then $$\sum_{r=0}^{l-j}\,(-1)^r\,\binom{l-j}{r}\,(r+j)\,\left(\frac{j}{l}\right)^{r}=l\,.$$ If $j<l$, then \begin{align} \sum_{r=0}^{l-j}\,(-1)^r\,\binom{l-j}{r}\,r\,\left(\frac{j}{l}\right)^{r}&=-(l-j)\left(\frac{j}{l}\right)\,\sum_{r=1}^{l-j}\,(-1)^{r-1}\,\binom{l-j-1}{r-1}\,\left(\frac{j}{l}\right)^{r-1} \\&=-j\left(1-\frac{j}{l}\right)\,\left(1-\frac{j}{l}\right)^{l-j-1}=-j\left(1-\frac{j}{l}\right)^{l-j} \end{align} and $$\sum_{r=0}^{l-j}\,(-1)^r\,\binom{l-j}{r}\,j\left(\frac{j}{l}\right)^r=j\left(1-\frac{j}{l}\right)^{l-j}\,.$$ Consequently, $$\sum_{r=0}^{l-j}\,(-1)^r\,\binom{l-j}{r}\,(r+j)\,\left(\frac{j}{l}\right)^{r}=\begin{cases} 0\,,&\text{if }j<l\,,\\ l\,,&\text{if }j=l\,. \end{cases}$$ From (*), $$\sum_{k=1}^l\,\binom{l-1}{k-1}\,\frac{b_k}{l^k}=\frac{a_l}{l}\,\binom{l-1}{l-1}\,\left(\frac{l}{l}\right)^l\,l=a_l\,.$$

• Thank you very much for the detailed proof. I have to check, if I understand everything because it’s not simple. Aug 25 '16 at 7:47