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!


3 Answers 3


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}.$$

  • $\begingroup$ Such a wonderful solution! Thank you so much. $\endgroup$
    – Libli
    Oct 16, 2021 at 9:11

It can be seen that the left-hand side for $j<n$ equals the coefficient of $x^j$ in $$\frac12(1+\sqrt{1+x})^n=\frac12\left(\frac2{C(\tfrac{-x}4)}\right)^n,$$ where $C(x):=\frac{1-\sqrt{1-4x}}{2x}$ is the generating function for Catalan numbers (enumerating Dyck paths). It remains to use the formula $[x^k]\ C(x)^m = \frac{m}{2k+m}\binom{2k+m}{k}$ for $k=j$ and $m=-n$ to obtain the formula in the question.

This proof suggests us to look for combinatorial interpretation in terms of Dyck paths.

PS. This formula can also be seen from formula (5.75) in the Concrete Mathematics book.


Here is an alternative (algebraic) proof based on the Wilf-Zeilberger technique.

Define two functions (suppressing $j$):

\begin{align*} F(n,k)&=\binom{k}j\binom{n}{2k}2^{2j+1-n}\frac{(n-j)}{n\binom{n-j}j} \qquad \text{and} \\ G(n,k)&=-\frac{F(n,k)(k-j)(2k-1)}{(n-j)(n-2k+1)}. \end{align*}

Your identity amounts to $\sum_{k=j}^{\lfloor\frac{n}2\rfloor}F(n,k)=1$. Next, verify that $$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$ and then sum over all integers $k$. The right-hand side vanishes which leads to $\sum_kF(n,k)$ being a constant. The case $n=1$ readily gives the value $1$. The proof is complete.

Note. It'd still be desirable to have a combinatorial proof.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.