QUESTION. Is there a combinatorial proof of the below identity? $$\sum_{k=0}^{n-1}\frac{2^{2k}}{2k+1}\frac{\binom{2n}n}{\binom{2k}k}=2^{2n}-\binom{2n}n.$$
REMARK. There are many other proofs (algebraic, analytic, etc).
$\begingroup$
$\endgroup$
7
asked Dec 5, 2020 at 15:57
-
2$\begingroup$ Dividing by $\binom{2n}{n}$ and applying the natural inductive argument reduces this to the identity $(\star) \, \binom{2(n+1)}{n+1}(n+1) = \binom{2n}{n} 2(2n+1)$. So perhaps an easier problem is first finding a combinatorial proof of $(\star)$. $\endgroup$– Ofir GorodetskyCommented Dec 5, 2020 at 16:08
-
2$\begingroup$ @Ofir Gorodetsky: the identity $(\star)$ is also the inductive step for $4^n=\sum_{i}{2i \choose i}{2n-2i\choose n-i } $, which has a story of combinatoric interpretations (Richard Stanley in Enumerative Combinatorics quotes a couple of papers, and there are also some questions on it here on MO). $\endgroup$– Pietro MajerCommented Dec 5, 2020 at 16:54
-
$\begingroup$ An equivalent form of $(\star)$ is ${2n+2\choose n+1}{n+1\choose2}={2n \choose n}{2n+1\choose2}$, which is also tempting. $\endgroup$– Pietro MajerCommented Dec 5, 2020 at 17:01
-
4$\begingroup$ @OfirGorodetsky we may count such things: divide $2n+2$ students to two groups each consistent of $n+1$ students and choose a leader in each group. If we start with choosing the division by groups, this gives ${2(n+1)\choose n+1}(n+1)^2$ variants. If we start with choosing two leaders, this gives $(2n+2)(2n+1){2n\choose n}$. So we get your $(\star)$ multiplied by $n+1$. $\endgroup$– Fedor PetrovCommented Dec 5, 2020 at 17:28
-
1$\begingroup$ @FedorPetrov Of course (I forgot to mention that). But what I'd really like to learn is a method to make an interpretation of the identity $\sum_i{2i \choose i }{2n-2i\choose n-i}=4^n$ (or of the OP's) out of the natural interpretation of $(\star)$. $\endgroup$– Pietro MajerCommented Dec 5, 2020 at 17:40
|
Show 2 more comments