Counting hyperplane cuts vs. projections. Combinatorial identity

Question

I have checked the following combinatorial identity for several cases and it seems to work. I would like to know if this is known or if there is a counter-example. Note, i is a given constant.

$$(i+d)\sum_{k\geq d} a_k\binom{k-d}{i} = \sum_{l=1}^{d} n_l \sum_{k\geq d} b_{k,l}\binom{k-d}{i}$$

$$a_k=| \{ (i_1,..,i_d) \in [n_1]\times...\times[n_d]:\sum_{j=1}^d i_j=k \}|$$

$$b_{k,l}=|\{(i_1,..i_{l-1},n_l,i_{i+1},..,i_d) \in [n_1]\times...\times[n_d]:\sum_{j=1}^d i_j=k\}|$$

I have been thinking about the left as some weighting on the compositions that come from cutting the space by a hyperplane. The right looks like some kind of weighted projection summation.

Answer 1

So, given numbers $d, n_1,\dots,n_d\in \mathbb N$, we define the polynomial $$P(x)=\frac{1}{x^d}\prod_{i=1}^d (x+x^2+\cdots+x^{n_i})$$ so that ` $$\sum_{k\geq 0}a_k\frac{(k-d)!}{(k-d-i)!}=\frac{d^{i}}{dx^{i}}P(x)\bigg| _{x=1}$$ Similarly we have $$\sum_{k\geq 0}b_{k-n _l,l}\frac{(k-d)!}{(k-d-i)!}=\frac{d^{i}}{dx^{i}}\left(\frac{x^{n_l}P(x)}{x+x^2+\cdots+x^{n_l}}\right)\Bigg| _{x=1}$$ So if we denote $$Q(x)=\sum_{l=1}^d \frac{n_lx^{n_l}}{x+x^2+\cdots+x^{n_l}}$$ your identity becomes equivalent to $$(d+i)\frac{d^{i}}{dx^{i}}P(x)\bigg| _{x=1}=\frac{d^{i}}{dx^{i}}P(x)Q(x)\bigg| _{x=1}$$ Now simply notice the following logarithmic derivative $\frac{P'(x)}{P(x)}=\frac{Q(x)-d}{x-1}$ which implies $$\frac{d^{i}}{dx^{i}}P(x)Q(x)\bigg| _{x=1}=\frac{d^{i}}{dx^{i}}P'(x)(x-1)+dP(x)\bigg| _{x=1}$$ $$=d\frac{d^i}{dx^i}P(x)\bigg| _{x=1}+i\frac{d^{i-1}}{dx^{i-1}}P'(x)\bigg| _{x=1}=(d+i)\frac{d^i}{dx^i}P(x)\bigg| _{x=1}$$ which is what we wanted to prove.

Answer 2

I believe this can be proved combinatorially. Consider we are working in the $[n_1]\times ... \times [n_d]$ box. Consider attaching a variable to each coordinate. Then consider picking an $S=i_1*x_1,...,i_d*x_d$. Then pick a set $X$ consisting of monomials s.t. the coefficient on the monomials is less than the coefficients given in $S$, $S$ is a subset of $X$, and $|X|=i+d$. Then pick a particular element of $X$ as special. This is the left hand side. $$$$ Then consider picking a special monomial in this set. Say this is in the variable $x_l$ Then pick $S_*=i_1*x_1,..,i_{l-1}*x_{l-1},i_{l+1}*x_{l+1},..,i_d*x_d$. Note this leaves the coefficient on $x_l$ unbounded. Then pick the set $X$ s.t. the coefficients on monomials in $X$ are bounded by $S_* $'s monomial coefficients, $S_* $ and the special monomial are in $X$, and $|X|=i+d$. This is the right hand side. $$$$ Both of these count unique sets $X$ with a special monomial, hence they are equal.