3
$\begingroup$

$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)?

Thanks in advance.


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$ .

$\endgroup$
  • 3
    $\begingroup$ "obviously"? $ $ $\endgroup$ – Henry Swanson Aug 25 '16 at 0:09
  • $\begingroup$ With examples. :-) $\endgroup$ – user90369 Aug 25 '16 at 7:33
1
$\begingroup$

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\,.$$

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

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}.$$

Adding the two components yields

$$\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.

$\endgroup$
  • $\begingroup$ Thank you very much for your efforts! Seems to be right but I have to check, if I understand everything. $\endgroup$ – user90369 Aug 25 '16 at 7:52
  • $\begingroup$ +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. $\endgroup$ – Felix Marin Aug 25 '16 at 23:30
  • $\begingroup$ @Felix Marin : Yes, such problems are assigned to discrete mathematics. $\endgroup$ – user90369 Aug 26 '16 at 7:40
  • $\begingroup$ There is a similar relation in Donald Knuth et.al. $\texttt{Concrete Mathematics}$ book: Formula $\mathbf{5.48}$ in page 192. $\endgroup$ – Felix Marin Aug 29 '16 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.