## Proof of a combinatorial identity (possibly using trigonometric identities)

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

For integers $n \geq k \geq 0$, can anyone provide a proof for the following identity?

$$\sum_{j=0}^k\left(\begin{array}{c}2n+1\\ 2j\end{array}\right)\left(\begin{array}{c}n-j\\ k-j\end{array}\right) = 2^{2k} \left(\begin{array}{c} n+k\\ 2k \end{array}\right)$$

I've verified this identity numerically for many values of $n$ and $k$, and suspect it to be true.

I found similar identities in http://www.math.wvu.edu/~gould/Vol.6.PDF, most notably:

$$\sum_{j=0}^k\left(\begin{array}{c}2n\\ 2j\end{array}\right)\left(\begin{array}{c}n-j\\ k-j\end{array}\right) = 2^{2k} \frac{n}{n+k}\left(\begin{array}{c} n+k\\ 2k \end{array}\right)$$

which is Eq. (3.20) in the above link, and

$$\sum_{j=0}^k\left(\begin{array}{c}2n+1\\ 2j+1\end{array}\right)\left(\begin{array}{c}n-j\\ k-j\end{array}\right) = 2^{2k} \frac{2n+1}{n-k}\left(\begin{array}{c} n+k\\ 2k+1 \end{array}\right)$$

which is Eq. (3.34) in the above link. The derivations of these two identities seem to rely on trigonometric identities, which I've been having trouble reconstructing.

-

4
math.upenn.edu/~wilf/AeqB.html – Steve Huntsman Jul 30 at 18:12

1
Maple knows this one: > sum(binomial(2*n+1,2*j)*binomial(n-j,k-j),j=0..k) assuming k::nonnegint, n::nonnegint,n>=k; $${\frac {{2}^{2\,k}\Gamma \left( 1+k+n \right) }{\Gamma \left( 2\,k+1 \right) \Gamma \left( n-k+1 \right) }}$$ – Robert Israel Jul 30 at 19:51

## 3 Answers

I'm surprised no one has posted a proof by double counting yet. First, I will rewrite the sum as $$F(n,k)=\sum_{j=0}^k\binom{2n+1}{2n-2j+1}\binom{n-j}{n-k}.$$ This counts the number of ways I can pick $2n-2j+1$ squares out of a $1\times (2n+1)$ grid, color them alternately black, white, black... etc. and then place a mark on $n-k$ white squares.

By deleting the first square as well as any immediate square following a marked white square we end up with a sequence of $n+k$ squares, $n-k$ of which are marked white squares and several others are colored.

Another way to count this is to choose the marked white squares first. This can be done in $\binom{n+k}{n-k}$ ways. And then specify the unmarked colored squares, this can be done in $2^{2k}$ ways. We get that $$F(n,k)=2^{2k}\binom{n+k}{n-k}$$ which is what we wanted.

Notice that I've left it as an exercise to show that deleting the squares is actually a bijection between the two sets, but this is quite easy to show. Indeed you only have to worry about adding back a square and deciding whether it should be colored or not. This can be done with a parity check on the number of colored boxes between consecutive marked boxes.

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

Let us compute the ordinary generating function of $k \mapsto c_{n+k,k}$, i.e. $S(X) = \sum_{k \geq 0 } c_{n+k,k} X^k$ (with notations as in Lierre's answer above) : $$S(X^2) = \sum_j \sum_k \binom{2n + 2k + 1}{2j} \binom{n+k-j}{k-j} X^{2k}$$ $$= \sum_j \sum_l \binom{2n + 2l + 2j + 1}{2j} \binom{n+l}{l} X^{2l+2j}$$ $$=\frac{1}{2} \sum_l \binom{n+l}{l} X^{2l} \sum_{\varepsilon = \pm 1} \sum_j \binom{2n + 2l + j + 1}{j} (\varepsilon X)^{j}$$ $$=\frac{1}{2} \sum_{\varepsilon = \pm 1} \sum_l \binom{n+l}{l} \frac{X^{2l}}{(1-\varepsilon X)^{2n+2l+2}}$$ $$=\frac{1}{2} \sum_{\varepsilon = \pm 1} \frac{1}{(1-\varepsilon X)^{2n+2}(1-\frac{X^2}{(1-\varepsilon X)^2})^{n+1}}$$ $$=\frac{1}{2} \sum_{\varepsilon = \pm 1} \frac{1}{(1- 2\varepsilon X)^{n+1}} =\sum_k \binom{n+2k}{2k} 2^{2k} X^{2k}$$ hence the result.

-

This is certainly not the proof you wanted, but it does work.

Let $a_{j,k,n}$ the term you want to sum, and let $b_{k,n}$ the right hand side. I denote by $S_x$ the shift operator w.r.t. the variable $x$. For example $S_k \cdot a_{j,k,n} = a_{j,k+1,n}$.

You can check that $$\left((-1+k-n)S_n+(1+k+n)\right)\cdot a_{j,k,n} = (S_j-1)\cdot \left(\frac{-j+2 j^2}{-3+2 j-2 n} a_{j,k,n}\right)$$ and $$\left((1 + 3 k + 2 k^2)S_k + (2 k + 2 k^2 - 2 n - 2 n^2)\right)\cdot a_{j,k,n} = (S_j-1)\cdot \left( \frac{\left(-j+2 j^2\right) (k-n)}{-1+j-k} a_{j,k,n}\right).$$

What is interesting in these identities is that the right hand side is zero when you sum over $j$ from $0$ to $k$. More over, the operators on the left hand side does not contain $j$, so they commute with the summation w.r.t. $j$.

In the end, you obtain that the sum $c_{k,n} = \sum_{k=0}^n a_{j,k,n}$ satisfies the recurrence relations $$\left((-1+k-n)S_n+(1+k+n)\right)\cdot c_{k,n} = 0$$ and $$\left((1 + 3 k + 2 k^2)S_k + (2 k + 2 k^2 - 2 n - 2 n^2)\right)\cdot c_{k,n} = 0.$$

These recurrence relations are also satisfied by $b_{k,n}$ ! With a careful checking of some initial conditions, this is enough to prove the equality.

I did not compute by hand these so called telescoping relations, Mathematica did, with the package HolonomicFunctions.

`CreativeTelescoping[Binomial[2 n + 1, 2 j]*Binomial[n - j, k - j], S[j] - 1, {S[k], S[n]}]`

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 24, "mathjax_display_tex": 16, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9336754679679871, "perplexity_flag": "head"}