Double-counting proof of $\left( \! \binom{n}{2m+1} \! \right)=\sum_{k=1}^n \left( \! \binom{k}{m} \! \right)\left( \! \binom{n-k+1}{m} \! \right) $

Question

I am trying to do a double-counting proof of $$\left( \! \binom{n}{2m+1} \! \right)=\sum_{k=1}^n \left( \! \binom{k}{m} \! \right)\left( \! \binom{n-k+1}{m} \! \right)$$ where $n,m\in\Bbb N$ (where $0\in\Bbb N$).

From the enumerative combinatorics class I am taking, we know that $\left( \! \binom{n}{2m+1} \! \right)$ counts the number of positive integer sequences $x_1,\ldots,x_{2m+1}$ such that $1\leq x_1\leq\cdots\leq x_{2m+1}\leq n$. So in my double counting proof, I want to answer the question "how many ways can we make a positive integer sequence $x_1,\ldots,x_{2m+1}$ such that $1\leq x_1\leq\cdots\leq x_{2m+1}\leq n$?", where one answer is clearly $\left( \! \binom{n}{2m+1} \! \right)$. The second answer is the part of the proof that I would like some feedback on (is it correct mainly).

Fix $k\in[n]$ (where $[n]:=\{1,2,\ldots,n\}$). Then there are $\left( \! \binom{k}{m} \! \right)$ positive integer sequences $y_1,\ldots,y_m$ such that $1\leq y_1\leq\cdots\leq y_m\leq k$. Similarly, there are $\left( \! \binom{n-k+1}{m} \! \right)$ positive integer sequences $z_1,\ldots,z_m$ such that $1\leq z_1\leq\cdots\leq z_m\leq n-k+1$. Manipulating this chain of inequalities we have $$1\leq z_1\leq\cdots\leq z_m\leq n-k+1\\-1\geq-z_1\geq\cdots\geq -z_m\geq k-n-1\\n\geq n+1-z_1\geq\cdots\geq n+1-z_m\geq k$$ setting $a_i:=n+1-z_{m-i+1}$ for $1\leq i\leq m$ yields $k\leq a_1\leq\cdots\leq a_m\leq n$. Note that the sequence $a_1,\ldots,a_m$ is a sequence of positive integers since $z_i\leq n\implies a_i=n+1-z_{m-i+1}\geq n+1-n=1$. Thus, combining the sequences we have $$1\leq y_1\leq\cdots\leq y_m\leq k\leq a_1\leq\cdots\leq a_m\leq n$$ Putting $x_i=y_i$ for $i\in\{1,2,\ldots,m\}$, $x_{m+1}:=k$, and $x_i:=a_{i-m-1}$ for $i\in\{m+2,m+3\ldots,2m+1\}$ yields a sequence we are looking for. Summing over all choices of $k$ yields $$\sum_{k=1}^n \left( \! \binom{k}{m} \! \right)\left( \! \binom{n-k+1}{m} \! \right)$$ total such sequences (as described above).

Is this proof correct? In particular, I am unsure about the combination of the $(z_i)$ sequence and the $(y_i)$ sequence into the $(x_i)$ sequence, and whether this actually covers all possible positive integer sequences as described. Thanks in advance for any feedback.

Answer 1

It is correct, but there is a slightly simpler way of formulating it. We are counting the number of sequences in $[n]$ of length $2m+1$. Let $1 \leq x_1 \leq \dots \leq x_{2m+1} \leq n$ be any such sequence. Assume that the middle element of the sequence $x_{m+1}$ is $k$. The remaining elements form two sequences of length $m$, $1 \leq x_1 \leq \dots \leq x_m \leq k$ and $k \leq x_{m+2} \leq \dots \leq x_{2m+1} \leq n$. We have $1 \leq x_{m+2}-(k-1) \leq \dots \leq x_{2m+1}- (k-1) \leq n-k+1$. Now summing over all choices of $k$ gives the result.