summation of a weighted product of binomial coefficients

124 Views Asked by At

Does anyone know how to prove that $$\sum\limits_{k=0}^i (-1)^k \frac{\binom{m-k}{k}}{(m-k)}\frac{\binom{m+2i-2k}{i-k}}{(m+2i-2k)}=0$$ for all $1\leq i\leq\lfloor\frac{m}{2}\rfloor$?

A calculation by Macaulay2 shows that $$\sum\limits_{k=0}^i (-1)^k \binom{m-k}{k}\binom{m+2i-2k}{i-k}=\sum\limits_{k=0}^i\binom{2i}{k}$$ but I don't know how to prove it neither and I don't know if it helps.

2

There are 2 best solutions below

0
On BEST ANSWER

We seek to prove that $$ \sum\limits_{k=0}^i (-1)^k \frac{1}{m-k}\binom{m-k}{k}\frac{1}{m+2i-2k}\binom{m+2i-2k}{i-k}=0 $$ for all $1\le i\le\left\lfloor\frac{m}{2}\right\rfloor$.

Let $a_i$ be the left-hand side of the above equation, and let $$ b_k=\frac{1}{m-k}\binom{m-k}{k}, \qquad c_k=\frac{1}{m+2k}\binom{m+2k}{k}, $$ then $a_i=\sum_{k=0}^{i}{(-1)^k b_k c_{i-k}}$. Let $A(x)=\sum_{i=0}^{\infty}a_ix^i$, $B(x)=\sum_{i=0}^{\infty}b_ix^i$, $C(x)=\sum_{i=0}^{\infty}c_ix^i$, then $A(x)=B(-x)C(x)$. (Note that $B(x)$ is just a polynomial, since $b_k=0$ for $k>\left\lfloor\frac{m}{2}\right\rfloor$.)

It is well-known that $C(x)=\frac{1}{m}\operatorname{Cat}(x)^m$, where $\operatorname{Cat}(x)$ is the Catalan generating function. To verify that, let $f(x)=\operatorname{Cat}(x)-1$ and note that $mc_k=[x^k](f+1)^m$, where $f$ satisties the functional equation $f=x(f+1)^2$. Then Lagrange inversion yields $$ \begin{split} mc_k=[x^k](f+1)^m&=\frac{1}{k}[f^{k-1}](f+1)^{2k}m(f+1)^{m-1}=\frac{m}{k}[f^{k-1}](f+1)^{m-1+2k}\\ &=\frac{m}{k}\binom{m-1+2k}{k-1}=\frac{m}{m+2k}\binom{m+2k}{k}. \end{split} $$ Similarly, $$ \begin{split} mb_k&=\frac{m}{m-k}\binom{m-k}{k}=\frac{m}{k}\binom{m-1-k}{k-1}\\ &=\frac{m}{k}[f^{k-1}](f+1)^{m-1-k}=\frac{1}{k}[f^{k-1}]\frac{1}{(f+1)^k}m(f+1)^{m-1}, \end{split} $$ where the second line holds for $1\le k\le \left\lfloor\frac{m}{2}\right\rfloor$. Thus, for $1\le k\le \left\lfloor\frac{m}{2}\right\rfloor$, $mb_k=[x^k](f+1)^m$ for a function $f=f(x)$ that satisfies $f=\frac{x}{f+1}$, i.e. $f(f+1)=x$ (and $f(0)=0$), which means $f(x)=x\operatorname{Cat}(-x)$, so $$ B(x)=\frac{1}{m}(1+x\operatorname{Cat}(-x))^m+O\left(x^{\left\lfloor\frac{m}{2}\right\rfloor+1}\right)=\frac{1}{m\operatorname{Cat}(-x)^m}+O\left(x^{\left\lfloor\frac{m}{2}\right\rfloor+1}\right), $$ and therefore, $$ B(-x)=\frac{1}{m\operatorname{Cat}(x)^m}+O\left(x^{\left\lfloor\frac{m}{2}\right\rfloor+1}\right). $$ Thus, $$ A(x)=B(-x)C(x)=\frac{1}{m}\operatorname{Cat}(x)^m\left(\frac{1}{m\operatorname{Cat}(x)^m}+O\left(x^{\left\lfloor\frac{m}{2}\right\rfloor+1}\right)\right)=\frac{1}{m^2}+O\left(x^{\left\lfloor\frac{m}{2}\right\rfloor+1}\right), $$ and therefore, $a_n=[x^n]A(x)=0$ for $1\le n\le \left\lfloor\frac{m}{2}\right\rfloor$, as desired.

0
On

We seek to prove with $n\ge 1$ and $2n\le m$ that

$$\sum_{k=0}^n (-1)^k \frac{1}{m-k} {m-k\choose k} \frac{1}{m+2n-2k} {m+2n-2k\choose n-k} = 0.$$

Observe that

$$\frac{1}{m-k} {m-k\choose k} = \frac{1}{m} \left[ {m-k\choose k} + {m-1-k\choose k-1} \right]$$

and

$$\frac{1}{m+2n-2k} {m+2n-2k\choose n-k} = \frac{1}{m} \left[ {m+2n-2k\choose n-k} - 2 {m+2n-1-2k\choose n-k-1} \right].$$

Therefore it is sufficient to prove that

$$\sum_{k=0}^n (-1)^k \left[ {m-k\choose k} + {m-1-k\choose k-1} \right] \\ \times \left[{m+2n-2k\choose n-k} - 2{m+2n-1-2k\choose n-k-1}\right] = 0.$$

We get four pieces, the first is

$$\sum_{k=0}^n (-1)^k {m-k\choose k} {m+2n-2k\choose n-k} \\ = [z^n] (1+z)^{m+2n} \sum_{k\ge 0} (-1)^k {m-k\choose m-2k} \frac{z^k}{(1+z)^{2k}}.$$

Here we have extended to infinity due to the coefficient extractor. Continuing,

$$[z^n] (1+z)^{m+2n} [w^m] (1+w)^m \sum_{k\ge 0} (-1)^k \frac{w^{2k}}{(1+w)^k} \frac{z^k}{(1+z)^{2k}} \\ = [z^n] (1+z)^{m+2n} [w^m] (1+w)^m \frac{1}{1+w^2z/(1+w)/(1+z)^2}.$$

We get for the next piece

$$\sum_{k=0}^n (-1)^k {m-1-k\choose k-1} {m+2n-2k\choose n-k} \\ = [z^n] (1+z)^{m+2n} [w^m] (1+w)^{m-1} \frac{1}{1+w^2z/(1+w)/(1+z)^2}.$$

The third piece is

$$-2\sum_{k=0}^n (-1)^k {m-k\choose k} {m+2n-1-2k\choose n-1-k} \\ = -2 [z^{n-1}] (1+z)^{m+2n-1} [w^m] (1+w)^m \frac{1}{1+w^2z/(1+w)/(1+z)^2}.$$

The fourth and last piece is

$$-2\sum_{k=0}^n (-1)^k {m-1-k\choose k-1} {m+2n-1-2k\choose n-1-k} \\ = -2 [z^{n-1}] (1+z)^{m+2n-1} [w^m] (1+w)^{m-1} \frac{1}{1+w^2z/(1+w)/(1+z)^2}.$$

Adding the four pieces we obtain

$$[z^{n}] (1+z)^{m+2n-1} [w^m] (1+w)^{m-1} \frac{1}{1+w^2z/(1+w)/(1+z)^2} \\ \times \left[ (1+z)(1+w) + (1+z) - 2z(1+w) - 2z \right] \\ = [z^{n}] (1+z)^{m+2n+1} [w^m] (1+w)^m \frac{(1-z)(2+w)}{(1+w)(1+z)^2+w^2z} \\ = [z^{n}] (1+z)^{m+2n+1} [w^m] (1+w)^m \frac{(1-z)(2+w)}{(w+1+z)(wz+1+z)} \\ = [z^{n+1}] (1+z)^{m+2n+1} [w^m] (1+w)^m \frac{(1-z)(2+w)}{(w+1+z)(w+(1+z)/z)}.$$

The contribution from $w$ is

$$\;\underset{w}{\mathrm{res}}\; \frac{1}{w^{m+1}} (1+w)^m \frac{2+w}{(w+1+z)(w+(1+z)/z)}.$$

Here the residue at infinity is zero and we may use minus the residues at $w=-(1+z)$ and $w=-(1+z)/z.$ We get for the former

$$- [z^{n+1}] (1+z)^{m+2n+1} \frac{(-1)^{m+1}}{(1+z)^{m+1}} (-1)^m z^m \frac{(1-z)^2}{-(1+z)+(1+z)/z} \\ = [z^{n+1}] (1+z)^{2n} z^{m+1} \frac{(1-z)^2}{1-z^2} = [z^n] (1+z)^{2n-1} z^m (1-z) = 0.$$

This is zero because $m\gt n$ due to the prerequisites. In fact we even have $m\ge 2n.$ The second residue yields

$$- [z^{n+1}] (1+z)^{m+2n+1} \frac{(-1)^{m+1} z^{m+1}}{(1+z)^{m+1}} \frac{(-1)^m}{z^m} \frac{(1-z) (2-(1+z)/z)}{-(1+z)/z+1+z} \\ = [z^{n+1}] (1+z)^{2n} z \frac{(1-z)^2}{1-z^2} = [z^n] (1+z)^{2n-1} (1-z) \\ = {2n-1\choose n} - {2n-1\choose n-1} = 0.$$

This concludes the argument.