Proving an identity with combinatorics

85 Views Asked by At

Assuming $n \in \mathbb{N}$ even and $l \in \mathbb{N}$ such that $l \geq \frac{n}{2}$, I want to show that:

$$ \frac{ {n\choose l} }{ {n/2\choose \lfloor l/2 \rfloor }^2 } \sum_{k=0}^{n-l} (-2)^{k} \frac{ {n-k\choose l} }{ {n \choose k} } \sum_{i=0}^{k} \frac{ {n/2\choose i}^2 {n/2\choose k-i}^2 }{ {k\choose i} } = \begin{cases} 1 &\text{ for $l$ even} \\ 0 & \text{ for $l$ odd } \end{cases} $$

I tested it numerically and it seems to hold. I tried to use Gould's combinatorial identities to simplify it but there is no matching formula I believe. For those interested, it comes from equaling two polynomials (one expressed in the canonical basis and the other expressed in the Laguerre basis) and I believe this is the easiest equality to show.

1

There are 1 best solutions below

0
On

I could not find an analytical way to prove the relation but I could prove it on Mathematica using the following:

https://www3.risc.jku.at/research/combinat/software/ergosum/RISC/fastZeil.html

First I redecomposed the above double sum in order to have one sum on the LHS and one sum on the RHS (this is what you get by equaling the polynomial in the canonical basis - the double sum comes from equaling in the Laguerre basis). Then I have to prove equality between two sums. Zeilberger’s algorithm allows to find recurrence relation satisfied by the sum and if the recurrence relation is also satisfied for the other sum then we can conclude that the sums are equals (as the first terms are indeed equals).

Zeilberger’s algorithm is a really powerful algorithm to prove analytical relations.