I have noticed the following is true. Let's denote the equation below as (1) $$\sum_{k=1}^{d+1}(-1)^{d+1-k}\frac{1}{(d+1)(k-1)!(d+1-k)!}\prod_{i=1}^{d+1}\Big(\frac{q}{h}+(k-i)\Big)\prod_{j=k}^{d}\Big(1-jh\Big)\prod_{\ell=d-k+2}^{d}\Big(1+\ell h\Big).$$

Let's denote the equation below as (2) $$\sum_{k=1}^{d}(-1)^{d-k}\frac{1}{(d)(k-1)!(d-k)!}\prod_{i=1}^{d}\Big(\frac{q}{h}+(k-i)\Big)\prod_{j=1}^{d}\Big(1+(k-j)h\Big).$$

If I replace $q\, \text{by}\, \frac{1}{x-1}$ in eq(1)

and $q\text{by}\, 1/x$ and $h\,\text{by}\, \frac{(x-1)h}{x}$ in eq (2) we have tested for few values of $d$

$(x-1)^{d}\, eq(1) = x^d \,\text{eq (2)}$

Can I have a proof of this fact? Any help or why is true? Notice that eq (1) has $d+1$ terms and eq(2) has $d$ terms. So its seems like pascal triangle any combinatorial viewpoint?

  • $\begingroup$ What do you mean by, "... we have ..."? I wouldn't write "we have" unless I had a proof, but since you are asking for a proof, that can't be what you mean by "we have". So, what do you mean? $\endgroup$ Aug 22 '19 at 5:29
  • $\begingroup$ Sorry I have just done the computation for few values. I have the change the phrasing. Thanks for your comment. $\endgroup$
    – GGT
    Aug 22 '19 at 6:20
  • 1
    $\begingroup$ What are $h$ and $q$ in equations $1$ and $2$? Are they integers, rational numbers, real numbers, complex numbers, polynomials, or something else? Also, what is $x$ in $q=\tfrac{1}{x-1}$? Lastly, how can you set $h=\tfrac{(x-1)h}{x}$ in equation $2$? $\endgroup$
    – Servaes
    Aug 22 '19 at 7:45
  • $\begingroup$ Also, how are the parentheses placed around the products in equation $(1)$? Do you take the two products over $j$ for every value of $i$, or is it a product of three distinc products? That is to say, is it $$\prod_i\left(\prod_j\cdot\prod_j\right)\qquad\text{ or }\qquad \left(\prod_i\right)\cdot\left(\prod_j\right)\cdot\left(\prod_j\right).$$ $\endgroup$
    – Servaes
    Aug 22 '19 at 7:54
  • 1
    $\begingroup$ The origin of the expression is dealing with some Montone Hurwitz numbers. $\endgroup$
    – GGT
    Aug 30 '19 at 23:10

This is a partial answer; it gives a computer-aided proof (yes, the identity holds true).

Some cleanup first. We have $$\prod_{j=k}^{d}(1-jh)\prod_{\ell=d-k+2}^{d}(1+\ell h)=\frac{\prod_{\ell=-d}^{d}(1+\ell h)}{\prod_{j=1}^{d+1}\big(1+(j-k)h\big)},$$ so that $(1)$ equals $$\frac{\prod_{\ell=-d}^{d}(1+\ell h)}{(-h)^{d+1}(d+1)!}\sum_{k=0}^{d}(-1)^{d-k}\binom{d}{k}\prod_{j=0}^{d}\frac{(q/h)+k-j}{(-1/h)+k-j}.$$ Now, if we do all the suggested substitutions, denote $a=1/\big((x-1)h\big)$ and $b=-1/h$, and retain the (common) notation $\binom{x}{n}=\frac{x(x-1)\ldots(x-n+1)}{n!}$ for real $x$, we see the following needed to be proven.

Let $$F_d(a,b)=\sum_{k=0}^{d-1}(-1)^k\binom{d-1}{k}\binom{a+k}{d}\binom{b+k}{d},\\G_d(a,b)=\sum_{k=0}^{d-1}(-1)^k\binom{d-1}{k}\binom{a+k}{d}\Big/\binom{b+k}{d}.$$ Then $$F_d(a,a-b)=(-1)^{d+1}\binom{2d+1}{d}\binom{b+d}{2d+1}G_{d+1}(a,b).\tag{*}$$

I don't see an "elegant" proof yet. But the book linked above suggests methods to find recurrences satisfied by $F_d$ and $G_d$, via "telescoping" recurrences satisfied by the summands. Specifically, in our case we find $$d(a-b-d-1)(a-b+d+1)F_d(a,b)\\+(d+1)(2d+3)(a+b)F_{d+1}(a,b)\\+(d+1)(d+2)(d+3)F_{d+2}(a,b)=0$$ (using a computer) and $$(d-1)(d+1)G_d(a,b)\\+(2d+1)(b-2a)G_{d+1}(a,b)\\-(b-d-1)(b+d+1)G_{d+2}(a,b)=0.$$ Now it's easy to verify that $(\text{*})$ holds for $d\in\{1,2\}$, and that both sides of it satisfy the same recurrence.

  • $\begingroup$ The book mentioned the use of package also I can see telescoping series algorithm. Is there any way I can put (*) in maple and verify directly? How do you derive the recursion? Using package or by hand? $\endgroup$
    – GGT
    Sep 3 '19 at 5:30
  • $\begingroup$ Regarding the direct verification of (*) - indeed, one can put it into a single sum; gonna try it myself once I get back (I don't have Maple installed on my personal machine). Yes, I've ended up using the package, after initial results from WA. $\endgroup$
    – metamorphy
    Sep 3 '19 at 8:07
  • $\begingroup$ Thanks update me if you have success What is WA? $\endgroup$
    – GGT
    Sep 3 '19 at 23:15
  • $\begingroup$ Well, nope. Although it "eats" both sides of $(\text{*})$ apart. To get the above, I load this (via read) and issue $$\texttt{zeil((-1)^k*binomial(d-1,k)*binomial(a+k,d)*binomial(b+k,d),k,d,D)}$$ and the like. (Just in case you try it too.) WA is Wolfram Alpha. $\endgroup$
    – metamorphy
    Sep 4 '19 at 6:07
  • $\begingroup$ You save the EKHAD as text file in maple folder? It keep complaining can read file. $\endgroup$
    – GGT
    Sep 4 '19 at 12:30

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.