Timeline for Asking for a combinatorial proof of a binomial-sum
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 8, 2020 at 4:59 | comment | added | Alexander Burstein | Maybe divide through by $\binom{2n}{n}$ and think of a probabilistic argument involving, say, increasing binary trees vs. increasing ternary trees? This is very half-baked, though. | |
| Dec 5, 2020 at 17:40 | comment | added | Pietro Majer | @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)$. | |
| Dec 5, 2020 at 17:28 | comment | added | Fedor Petrov | @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$. | |
| Dec 5, 2020 at 17:15 | comment | added | Mark Wildon | Since $\binom{2n}{n}/\binom{2k}{k}$ is typically not an integer, maybe this is not the best form to start with when asking for a combinatorial proof? Particularly since I interpret this as asking for a bijective proof, for preference. (I'm sure you can easily prove the identity using generating functions, or by the inductive approach indicated in Ofir Gorodetsky's comment.) | |
| Dec 5, 2020 at 17:01 | comment | added | Pietro Majer | An equivalent form of $(\star)$ is ${2n+2\choose n+1}{n+1\choose2}={2n \choose n}{2n+1\choose2}$, which is also tempting. | |
| Dec 5, 2020 at 16:54 | comment | added | Pietro Majer | @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). | |
| Dec 5, 2020 at 16:08 | comment | added | Ofir Gorodetsky | 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)$. | |
| Dec 5, 2020 at 15:57 | history | asked | T. Amdeberhan | CC BY-SA 4.0 |