Intereting Posts

Is this sum related to the Gregory's limit?
$L^p$ implies polynomial decay?
A unsolved puzzle from Number Theory/ Functional inequalities
How to prove $\left(1+\frac{1}{\sin a}\right)\left(1+\frac{1}{\cos a}\right)\ge 3+2\sqrt{2}$?
Projection formula, Bott and Tu
Alternative form to express the second derivative of $\zeta (2) $
Are these numbers $h_{r,s}$ irrational?
Calculate the slope of a line passing through the intersection of two lines
Is it necessary for the homsets to be disjoint in a category?
Evaluating the sum of geometric series
How to compute intersection multiplicity?
homomorphism of Laurent polynomial ring
Which of the following subsets of $\mathbb{R}^2$ are compact
Is it true that any metric on a finite set is the discrete metric?
$f'$ exists, but $\lim \frac{f(x)-f(y)}{x-y}$ does not exist

I am trying to get a combinatorial proof for this summation identity, for $0\leq k\leq \frac{n}{2}$

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

The way I interpreted is that, for the right hand side $\binom{n+1}{2k+1}$ is the number of ways to choose $2k+1$ from total of $n+1$, then for left hand side, condition on dividing $n+1$ into two groups of size $m+1$ and $(n+1)-(m+1)=n-m$, then if choose $k$ the group of $n-m$ then it gives $\binom{n-m}{k}$, so there are $2k+1-k=k+1$ to choose from the group of size $m+1$, this is $\binom{m+1}{k+1}$, therefore I got the left hand side as $\sum_{m=k}^{n-k}\binom{m+1}{k+1}\binom{n-m}{k}\neq\sum_{m=k}^{n-k}\binom{m}{k}\binom{n-m}{k}$. what did I do wrong here? please help.

- proving that $\frac{(n^2)!}{(n!)^n}$ is an integer
- How to find a linear extension of a poset
- In how many ways can we colour $n$ baskets with $r$ colours?
- A variant of assignment problem (different sizes of sets)
- A question about combinatorics
- Knight returning to corner on chessboard — average number of steps

- Proof of a combinatorial identity: $\sum\limits_{i=0}^n {2i \choose i}{2(n-i)\choose n-i} = 4^n$
- Maximal unit lengths in 3D with $n$ points.
- What is the probability of the sum of four dice being 22?
- Intuitively understanding $\sum_{i=1}^ni={n+1\choose2}$
- Count ways to take pots
- Number of ways to pair off $2n$ points such that no chords intersect
- Arrangement of $100$ points inside $13\times18$ rectangle
- Counting Binary Strings (No block decompositions)
- What is the rank of COCHIN
- In how many ways can a $31$ member management be selected from $40$ men and $40$ women so that there is a majority of women?

Suppose that you pick a set $A$ of $2k+1$ members of the set $[n+1]=\{1,\dots,n+1\}$. Let $A=\{a_0,\dots,a_{2k}\}$, where $a_0<a_1<\ldots<a_{2k}$. Then $k$ members of $A$ are less than $a_k$, and $k$ are greater. Let $A_0=\{a_0,\dots,a_{k-1}\}$ and $A_1=\{a_{k+1},\dots,a_{2k}\}$. Clearly $A_0\subseteq[a_k-1]$, so there are $\binom{a_k-1}k$ possibilities for $A_0$. Similarly, $A_1\subseteq[n+1]\setminus[a_k]$, so there are $\binom{n+1-a_k}k$ possibilities for $A_1$. Thus, for a fixed value $\ell$ of $a_k$ there are

$$\binom{\ell-1}k\binom{n+1-\ell}k\tag{1}$$

possible $(2k+1)$-subsets $A$ of $[n+1]$. The minimum possible value of $\ell$ is $k+1$, since there must be at least $k$ smaller numbers in $[n+1]$, and the largest possible value is $n+1-k$. Let $m=\ell-1$; then $m$ ranges from $k$ through $n-k$, the expression $(1)$ becomes

$$\binom{m}k\binom{n-m}k\;,\tag{2}$$

and it’s now clear that summing $(2)$ from $m=k$ to $m=n-k$ is counting the $(2k+1)$-subsets of $[n+1]$ according to their middle elements.

In your approach you are in effect looking only at $A_0$ and $A_1$, but they don’t tell you where the cutoff between them is $-$ the $a_k$ in my construction.

The way you are trying to set of things, there is no way to recover the value of $m$ from the subset chosen in the right hand side, so several choices of $m$ may lead to the same subset, and you’re overcounting.

However if you take $m$ to be equal to the middle element *of the selected subset* taken in increasing order (that is the $k+1$-st smallest one), then you solve two difficulties: you can recover $m$ from the choice, and there remain onle $k$ elements to choose on either side of that value $m$. See this answer for handling a somewhat more general identity.

- Recurrence Relation Solving Problem
- Solve $A^nx=b$ for an idempotent matrix
- Size of a family of sets $F$ such that if $|A\cap X|=|B\cap X|$ for all $X\in F$, then $A=B$
- Conditions for free/projective/flat module over a groupring
- Constructiveness of Proof of Gödel's Completeness Theorem
- General expression of $f(a, b)$ if $f(a, b)=f(a-1,b) + f(a, b-1) + f(a-1, b-1)$?
- Is compactness a stronger form of continuity?
- When is $2^n \pm 1$ a perfect power
- Is Proof by Resolution really needed here?
- the sum of a series
- fair and unfair games
- Relationship between $\tanh x$ and $\arctan x$
- A combinatorial proof of $\forall n\in\mathbb{N},\,\binom{n}{2}=\frac{n(n-1)}{2}$
- Number of rooted subtrees of given size in infinite d-regular tree
- Radial Limits for Holomorphic Functions