I have asked this question 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!
Best Answer
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}.$$