15
$\begingroup$

While exploring the Baxter sequences from my earlier MO post, I obtained a rather curious identity (not listed on OEIS either). I usually try to employ the Wilf-Zeilberger (WZ) algorithm to justify such claims. To my surprise, WZ offers two different recurrences for each side of this identity.

So, I would like to ask:

QUESTION. Is there a conceptual or combinatorial reason for the below equality? $$\frac1n\sum_{k=0}^{n-1}\binom{n+1}k\binom{n+1}{k+1}\binom{n+1}{k+2} =\frac2{n+2}\sum_{k=0}^{n-1}\binom{n+1}k\binom{n-1}k\binom{n+2}{k+2}.$$

Remark 1. Of course, one gets an alternative formulation for the Baxer sequences themselves: $$\sum_{k=0}^{n-1}\frac{\binom{n+1}k\binom{n+1}{k+1}\binom{n+1}{k+2}}{\binom{n+1}1\binom{n+1}2} =2\sum_{k=0}^{n-1}\frac{\binom{n+1}k\binom{n-1}k\binom{n+2}{k+2}}{\binom{n+1}1\binom{n+2}2}.$$

Remark 2. Yet, here is a restatement to help with combinatorial argument: $$\sum_{k=0}^{n-1}\binom{n+1}k\binom{n+1}{k+1}\binom{n+1}{k+2} =2\sum_{k=0}^{n-1}\binom{n+1}k\binom{n}k\binom{n+1}{k+2}.$$

$\endgroup$
2
  • $\begingroup$ This is now OEIS sequence A350265. $\endgroup$ Dec 29, 2021 at 9:24
  • $\begingroup$ @PeterLuschny: thank you! $\endgroup$ Dec 29, 2021 at 14:36

2 Answers 2

22
$\begingroup$

Just playing around with it: The RHS multiplied by $n$ is the same as

$$2 \sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n}{k} \binom{n+1}{k+2}.$$

Subtracting this from $n$ times the LHS gives

$$\sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n+1}{k+2} \left( \binom{n}{k+1} - \binom{n}{k} \right).$$

Now you check that replacing $k$ with $n-1-k$ changes the sign of the summand, so the sum is zero.

$\endgroup$
11
$\begingroup$

The combinatorial identity $$ \sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n+1}{k+1} \binom{n+1}{k+2} = 2 \sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n}{k} \binom{n+1}{k+2} $$ has a simple combinatorial proof.

The left-hand side counts all triples $A,B,C \subseteq [n+1]$ whose sizes are $k,k+1,k+2$ for some $k$. These come in two types:

  • $n+1 \in B$. The triple $A,B\setminus\{n+1\},C$ has sizes $k,k,k+2$, and the middle set is a subset of $[n]$.
  • $n+1 \notin B$. The triple $\overline{C},\overline{B}\setminus\{n+1\},\overline{A}$ has sizes $\bar{k},\bar{k},\bar{k}+2$, where $\bar{k}=n-1-k$, and the middle set is a subset of $[n]$.

The triples of each type are counted by the sum on the right-hand side.

$\endgroup$
1
  • $\begingroup$ This is essentially the same proof as Sean Eberhard's. $\endgroup$ Dec 24, 2021 at 12:41

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.