I have asked [this question](https://math.stackexchange.com/questions/4276271/chebyshev-polynomials-and-ballot-number) a short time ago on mathstackexchange, but it has already fallen into the abyss of answered and uncommented questions. So I take the risk to ask it on mathoverflow.


Playing with the various expressions 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 a useful interpreatation. Many thanks for your help!



Chebyshev polynomials and ballot numbers
Here is a combinatorial proof.


It is more convenient to prove the equivalent formula (obtained by setting $n=m+2j$)
$$\sum\_k \binom{k}{j}\binom{m+2j}{2k}=2^{m-1}\frac{m+2j}{m+j}\binom{m+j}{j}.\tag{$\*$}$$


To motivate the proof we first prove the closely related but slightly easier
formula
$$\sum\_k \binom{k}{j}\binom{m+2j+1}{2k+1} = 2^m\binom{m+j}{j}.\tag{1}$$


Let us first give a generating function proof of $(1)$. We start by multiplying the summand by $x^j y^m$ and summing on $j$ and $m$. We find that
$$
\sum\_{j,m}\binom{k}{j}\binom{m+2j+1}{2k+1} x^j y^m = \frac{(x+y^2)^k}{(1-y)^{2k+2}}
$$
and that
$$\sum\_{k=0}^\infty \frac{(x+y^2)^k}{(1-y)^{2k+2}}=\frac{1}{1-x-2y} = \sum\_{j,m}2^m\binom{m+j}{j}x^j y^m.\tag{2}$$
It is not hard to find objects counted by $2^m\binom{m+j}{j}$. We need to interpret $(x+y^2)^k/(1-y)^{2k+2}$ as counting some of these objects, and this is what the following proof does.


Let $S$ be the set of words in the the letters $x, y\_1, y\_2$ containing $j$ occurrences of $x$ and a total of $m$ occurrences of $y\_1$ and $y\_2$. There are $\binom{m+j}{m}$ words with $j$ occurrences of $x$ and $m$ occurrences of $y$. Each $y$ can be replaced with $y\_1$ or $y\_2$ so there are $2^m\binom{m+j}{m}$ words in $S$.


Now we count the words in $S$ in a different way. Let us define a *stopper* of a word in $S$ to be an occurrence of either $x$ or $y\_2y\_1$, and let us call the subwords before, between, and after the stoppers *segments*, so a word with $k$ stoppers has $k+1$ segments. Thus each segment is of the form $y\_1^a y\_2^b$, where $a$ and $b$ are nonnegative integers. For example, the word $y\_1 y\_2 x y\_2 y\_1 y\_2 y\_2x$ has three stoppers, $x$, $y\_2y\_1$, and $x$, and four segments, $y\_1y\_2$, $\varnothing$, $y\_2y\_2$, and $\varnothing$. (Here $\varnothing$ denotes the empty word.)


Let us count words in $S$ with $k$ stoppers (and thus $k+1$ segments). We must have $k\ge j$, since every $x$ is a stopper. Then there are $k-j$ stoppers of the form $y\_2y\_1$ so there are $m-2(k-j)$ occurrences of $y\_1$ and $y\_2$ among the $k+1$ segments. The segments are of the form $y\_1^{a\_0}y\_2^{b\_0},y\_1^{a\_1}y\_2^{b\_1},\dots,y\_1^{a\_k}y\_2^{b\_k}$, where $a\_0+b\_0+\cdots +a\_k+b\_k=m-2(k-j)$. The number of solutions in nonnegative integers of this equation is $\binom{m+2j+1}{2k+1}$
(since for fixed $r$ and $s$ the number of nonnegative integer solutions of $c\_1+c\_2+\cdots +c\_r = s$ is $\binom{r+s-1}{s}=\binom{r+s-1}{s-1}$).
Once the $a\_i$ and $b\_i$ are determined, the $k$ slots for the stoppers are fixed, and
we may decide which are $x$ and which are $y\_2y\_1$ in $\binom{k}{j}$ ways. Thus the number of elements of $S$ is
$$
\sum\_k \binom{k}{j}\binom{m+2j+1}{2k+1},
$$
which must also be equal to $2^m\binom{m}{j}$.


To prove the original identity $(\*)$, we replace $2k+2$ with $2k+1$ in the denominator of the left side of $(2)$. This corresponds to counting only those words in $S$ for which $a\_0=0$, i.e., the words in $S$ that do not start with $y\_1$. The number of solutions of $a\_0+b\_0+\cdots +a\_k+b\_k=m-2(k-j)$ with $a\_0=0$ is $\binom{m+2j}{2k}$, so the number of these words is the left side of $(\*)$. But (assuming $j$ and $m$ are not both 0) the number of words in $S$ that start with $y\_1$ is $2^{m-1}\binom{m+j-1}{j}$, so the number of words in $S$ that do not start with $y\_1$ is
$$2^j\binom{m+j}{j} -2^{m-1}\binom{m+j-1}{j} = 2^{m-1}\frac{m+2j}{m+j}\binom{m+j}{j}.$$


