# Equality like Pascal triangle

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?

• 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? Aug 22 '19 at 5:29
• Sorry I have just done the computation for few values. I have the change the phrasing. Thanks for your comment.
– GGT
Aug 22 '19 at 6:20
• 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$? Aug 22 '19 at 7:45
• 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).$$ Aug 22 '19 at 7:54
• The origin of the expression is dealing with some Montone Hurwitz numbers.
– 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.

• 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?
– GGT
Sep 3 '19 at 5:30
• 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. Sep 3 '19 at 8:07
• Thanks update me if you have success What is WA?
– GGT
Sep 3 '19 at 23:15
• 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. Sep 4 '19 at 6:07
• You save the EKHAD as text file in maple folder? It keep complaining can read file.
– GGT
Sep 4 '19 at 12:30