15
$\begingroup$

I'm facing the problem of trying to express a quantity in the simplest possible way (it is, using the least possible number of sum symbols).

$$ \sum_{j=0}^{n} \sum_{\ell=0}^m \frac{1}{j!}\binom{b+j}{j} {j+1 \brack {\ell+1}} {b+2 \brack {m-\ell+1}}$$

Of course, this can be easily written as a convolution between two polynomials (which happen to be more or less simple). I'm pretty sure that approach will not work (at most, one can write the above expression as "the coefficient of $x^m$ in this product [...]", but that is not useful to my purpose).

However, if one explores this sum a little bit, it pretty soon come up the fact that it could be truly useful to, for example, be able to compute this: $$\sum_{\ell=0}^m {j+1\brack{\ell+1}}{b+2 \brack {m-\ell+1}}$$ (which resembles a lot Vandermonde's Identity, but with Stirling numbers instead of binomial coefficients).

I looked up on a couple of books (Concrete Mathematics of Graham-Knuth-Patashnik, and others), and I couldn't find any references pointing to such an identity. Does anybody know something like that? (Perhaps involving other weird numbers as Eulerian or double Eulerian or that kind of stuff?)

Nevertheless, any kind of help simplifying the first double sum would be really appreciated.

$\endgroup$
9
  • 2
    $\begingroup$ The case $j=b=m$ yields OEIS A187235. $\endgroup$ Feb 16 '20 at 13:46
  • $\begingroup$ Do you want a simple or elementary answer? And a simple or elementary derivation? I think I can see a way forward but it involves several (elementary!) expansions and detours through calculus. Basically generate the generating function around the parameters b,m,n. Which will (?) generate first-order differential equations; that have to be reinserted in the first equation. I would guess that the answer would be some form of Generalized Hypergeometric Functions. Of course, I could be off-base :) $\endgroup$
    – rrogers
    Feb 19 '20 at 17:54
  • $\begingroup$ I don't mind if the derivation is hard (any kind of machinery is allowed). However, if the obtained formula ends up being a lot harder to compute than the original one, probably it wouldn't be so meaningful. Nevertheless, it may be the case that what you have is possibly useful, so please share it :) $\endgroup$ Feb 19 '20 at 19:50
  • $\begingroup$ Making progress; are you sure that "m" isn't constrained? Letting it get very large produce's large terms even for low "j". And your Stirling symbol means "unsigned Stirling", right? Is there any constraint on "B"? The binomial form can be thrown via the Riordan transform. With suitable constraints, a neat result can be fabricated, maybe. $\endgroup$
    – rrogers
    Feb 20 '20 at 17:04
  • $\begingroup$ I can post the primary tools I am using if you want. There are more than is convenient in comments. $\endgroup$
    – rrogers
    Feb 20 '20 at 17:06
7
+200
$\begingroup$

We show the following identity is valid for non-negative integers $a,b,M$: \begin{align*} \sum_{k=0}^M {a\brack k}{b\brack M-k}=\sum_{n=0}^{\min{\{a,b\}}}{a+b-n\brack M}\frac{(-1)^na!b!}{n!(a-n)!(b-n)!}\tag{1} \end{align*}

The right-hand sum is regrettably not a simplification. But we have at least one factor as Stirling number of the first kind instead of two (at the cost of some other factors) and we have an upper index containing $a+b$ which comes somewhat close to Vandermonde's identity \begin{align*} \sum_{k=0}^m\binom{a}{k}\binom{b}{M-k}=\binom{a+b}{M} \end{align*}

We show (1) by recalling the generating function: \begin{align*} (1-z)^{-u}=\sum_{n=0}^\infty\sum_{k=0}^n{n\brack k}u^k\frac{z^n}{n!}\tag{2} \end{align*}

At first we derive the left-hand side of (1). We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ and obtain from (2) \begin{align*} \color{blue}{a!b!}&\color{blue}{[u^Mz^at^b](1-z)^{-u}(1-t)^{-u}}\tag{3}\\ &=a!b![u^M]\left([z^a]\sum_{n=0}^\infty\sum_{k=0}^n{n\brack k}u^k\frac{z^n}{n!}\right)\left([t^b]\sum_{n=0}^\infty\sum_{k=0}^n{n\brack k}u^k\frac{t^n}{n!}\right)\\ &=a!b![u^M]\left(\sum_{k=0}^a{a\brack k}u^k\frac{1}{a!}\right)\left(\sum_{l=0}^b{b\brack l}u^l\frac{1}{b!}\right)\\ &=[u^M]\sum_{q=0}^{a+b}\sum_{{k+l=q}\atop{k,l\geq 0}}{a\brack k}{b\brack l}u^q\\ &=[u^M]\sum_{q=0}^{a+b}\sum_{k=0}^q{a\brack k}{b\brack q-k}u^q\\ &\,\,\color{blue}{=\sum_{k=0}^M{a\brack k}{b\brack M-k}}\tag{4} \end{align*}

We take (3) and calculate the coefficient in a somewhat different way.

We obtain \begin{align*} \color{blue}{a!b!}&\color{blue}{[u^Mz^at^b]((1-z)(1-t))^{-u}}\\ &=a!b![u^Mz^at^b](1-(z(1-t)+t))^{-u}\\ &=a!b![u^Mz^at^b]\left(\sum_{n=0}^\infty\sum_{k=0}^n{n\brack k}u^k\frac{(z(1-t)+t)^n}{n!}\right)\tag{5}\\ &=a!b![z^at^b]\sum_{n=0}^\infty{n\brack M}\frac{(z(1-t)+t)^n}{n!}\tag{6}\\ &=a!b![z^at^b]\sum_{n=0}^\infty{n\brack M}\frac{1}{n!}\sum_{j=0}^n\binom{n}{j}z^j(1-t)^jt^{n-j}\tag{7}\\ &=a!b![t^b]\sum_{n=0}^\infty{n\brack M}\frac{1}{n!}\binom{n}{a}(1-t)^at^{n-a}\tag{8}\\ &=a!b!\sum_{n=0}^{\min\{a,b\}}{n\brack M}\frac{1}{n!}\binom{n}{a}\binom{a}{a+b-n}(-1)^{a+b-n}\tag{9}\\ &=a!b!\sum_{n=0}^{\min\{a,b\}}{n\brack M}\frac{(-1)^{a+b-n}}{(n-a)!(n-b)!(a+b-n)!}\tag{10}\\ &\,\,\color{blue}{=a!b!\sum_{n=0}^{\min{\{a,b\}}}{a+b-n\brack M}\frac{(-1)^n}{n!(a-n)!(b-n)!}}\tag{11} \end{align*} and the claim (1) follows.

Comment:

  • In (5) we expand the series according to (2).

  • In (6) we select the coefficient of $u^M$.

  • In (7) we expand the binomial.

  • In (8) we select the coefficient of $z^a$.

  • In (9) we select the coefficient of $t^b$.

  • In (10) we do some cancellations.

  • In (11) we change the order of summation $n\to a+b-n$.

$\endgroup$
5
  • $\begingroup$ @LuisFerroni: Many thanks for granting the bounty. $\endgroup$
    – epi163sqrt
    Feb 23 '20 at 6:18
  • $\begingroup$ 1) Nice proof, much better than my futile attempts. 2) I was applying Zeilberg's algorithm (via Reduce) to apply binomial(b+a,b) to (9) (for a warmup to (b-3+a,b-2) ) and noticed that your transition (9) to (10) doesn't work. Consider n<a (i.e. n=1,a=10 or b=2) then the factorial interpretation of the binomial() blows up in (10). I think you have to go to the Gamma interpretation of the binomial when going from (9) to (10); to get zeros in the right place. $\endgroup$
    – rrogers
    Feb 27 '20 at 13:43
  • $\begingroup$ @rrogers: Thanks for your nice comment. Here I consider formal power series. So, a switch to Gamma function is for this kind of derivation not necessary. $\endgroup$
    – epi163sqrt
    Feb 27 '20 at 14:30
  • $\begingroup$ Okay, would you be upset if I posted the application of the binomial(b+a, a) to eliminate the "a"? Your development was really nice, in that exposed it. I have yet to be able to phrase the Stirling term but there is one clue. $\endgroup$
    – rrogers
    Feb 27 '20 at 15:21
  • $\begingroup$ @rrogers: This is fine for me. The more useful ideas are contributed, the better for the community. $\endgroup$
    – epi163sqrt
    Feb 27 '20 at 15:53
0
$\begingroup$

As usual check carefully (although there is a code snippet to illustrate).
I seem to have a form of mathematical dyslexia.
Answer: $\left[x^{M}\right]\frac{\Gamma\left(x+a\right)\Gamma\left(x+b\right)}{\Gamma\left(x\right)\Gamma\left(x+a+b\right)}\left(x\right)_{\left(a+b\right)}$
Actually the expression gives the answer for all $M$. Some code is included for that. I can expand it to include M and the binomial summation on a if needed. The process can probably be specialized to just compute one answer for a particular $M$. Let me know if you need it.

First some standard facts:
Definition 1. The Pochhammer symbol.

$$\begin{align*}\left(x\right)_{n}=x\cdot\left(x+1\right)\ldots\left(x+n-1\right) \end{align*}$$

Definition 2. Unsigned Stirling Number
$$\left[\begin{array}{c} n\\ l \end{array}\right]\equiv\left[x^{l}\right]{\displaystyle \prod_{k=0}^{n-1}\left(x+k\right)=\left[x^{l}\right]x\cdot\left(x+1\right)\ldots\left(x+n-1\right)}=\left[x^{l}\right]\left(x\right)_{n}$$
$$=\left[x^{l}\right]{\displaystyle \sum_{j=0}^{n}}\left[\begin{array}{c} n\\ j \end{array}\right]x^{j}$$

We can partition

$$\left(x\right)_{\left(a+b\right)}\rightarrow\left(x\right)_{a}\cdot\left(x+a\right)_{b} \tag{1}\label{1}$$

The formula for all convolutions:

$$(x)_{a}\cdot\left(x\right)_{b} \tag{2}\label{2}$$
The problem can be phrased as the convolution : $${\displaystyle {\displaystyle \sum_{j=0}^{min\left(a,b,M\right)}}\,\left[\begin{array}{c} a\\ j \end{array}\right]\left[\begin{array}{c} b\\ M-j \end{array}\right]}={\displaystyle \sum_{j=0}^{min\left(a,b\right)}}\left(\left[x^{j}\right]\left(x\right)_{a}\right)\cdot\left(\left[x^{M-j}\right]\left(x\right)_{b}\right)$$
$$=\left[x^{M}\right]\left(\left(x\right)_{a}\cdot\left(x\right)_{b}\right) \tag{2}\label{3}$$
Remark. The upper limit can be extended but additional terms would be zero.
The intent is to convert (1) to (2). Which can be done using:
http://functions.wolfram.com/06.10.17.0004.02
Substituting our symbols.
$$\left(x\right)_{b}=\frac{\Gamma\left(x+a\right)\Gamma\left(x+b\right)}{\Gamma\left(x\right)\Gamma\left(x+a+b\right)}\left(x+a\right)_{b}$$
Which is so obvious it's laughable.
Thus the answer is:
$$\left[x^{M}\right]\frac{\Gamma\left(x+a\right)\Gamma\left(x+b\right)}{\Gamma\left(x\right)\Gamma\left(x+a+b\right)}\left(x\right)_{\left(a+b\right)}=\left[x^{M}\right]\left(x\right)_{a}\cdot\left(x\right)_{b}$$
Maxima example code for all M:

load ("stirling")$
gamma_expand: true$
gamma(x+5);
p1:pochhammer(x,6);
expand(p1);
p2:pochhammer(x+a,6);
conv(a,b):=pochhammer(x,a+b)*gamma(x+a)*gamma(x+b)/((gamma(x))*gamma(x+a+b));
ratsimp(conv(4,5));
ratsimp(pochhammer(x,4)*pochhammer(x,5));

$\endgroup$

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.