0
$\begingroup$

I've come up with an interesting combinatorial identity (thanks to P. Belmans who precomputed the numbers and pointed out to me that they correspond to OEIS A002697):

$$ \sum_{i=0}^{n-1}\binom{n+1-i}{2}\binom{2n+1}{i} = n\cdot 4^{n-1}. $$

To me, the RHS has an obvious combinatorial interpretation. Namely, it is the number of ways to choose two intersecting subsets $X,Y\subset \{1, 2, \ldots, n\}$ and an element $x\in X\cap Y$.

I can prove the identity by hand, using induction. My question is whether there is a nice combinatorial proof of the identity above.

Edit: I forgot to mention that the LHS can be rewritten as $$ \frac{1}{2}\sum_{i=0}^{2n}(n-i)^2\binom{2n}{i}. $$

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I am guessing that $A=X$ and $B=Y$ and $g=n$; but please write the question more carefully. $\endgroup$
    – Neil Strickland
    Commented May 26, 2023 at 15:46
  • $\begingroup$ @NeilStrickland My bad! Fixed $\endgroup$
    – Anton Fonarev
    Commented May 26, 2023 at 15:56
  • 3
    $\begingroup$ It might be noted that the identity can be generalized to $$\sum_{i=0}^m \binom{m+a-i}{a}\binom{2m+a+1}{i} = 4^m\binom{m+a/2}{m}.$$ The original identity is the case $m=n-1, a=2$. $\endgroup$
    – Ira Gessel
    Commented May 26, 2023 at 16:19
  • $\begingroup$ By symmetry, your LHS rewrite is also $\sum_{i=0}^{n-1} (n-i)^2 \binom{2n}{i}$. $\endgroup$
    – RobPratt
    Commented May 26, 2023 at 17:21
  • 2
    $\begingroup$ Continuing from this, the L.H.S is $\frac{1}{2}(\sum_{i=0}^{2n} (2n-i)^2\binom{2n}{i}-n^24^n)=4^n\sigma^2_{2n}=n4^{n-1}$, (binomail varience) as $(n-i)$ is odd around $n$. $\endgroup$
    – Alapan Das
    Commented May 26, 2023 at 17:44

0

Reset to default

You must log in to answer this question.