Playing with the various expression of the Chebyshev polynomials of the first kind, I find for all $j \leq \lfloor \frac{n}{2} \rfloor$ the formula:

$$ \sum_{k=j}^{\lfloor \frac{n}{2} \rfloor} \binom{k}{j} \binom{n}{2k} = 2^{n-1-2j} \frac{n}{n-j} \binom{n-j}{j} $$

I would like to know if there is a (preferably simple) combinatorial proof of this formula. This looks like a Vandermonde type formula for some variant of the ballot numbers, but I don't know enough in this area to find the correct number. Many thanks for your help!



You must log in to answer this question.