Binomial Coefficient Summation Equivalence

Question

Following on a previous question, I'm supposed to prove the following: $$ \sum_{i=0}^{n-1} \binom{2n-2-i}{n-1} = \sum_{i=0}^{n-1} \binom{n-1+i}{i}.$$ Is there any simple conversion to come from the first term to the second one?

Answer 1

Note that $$\binom{m}{i}=\binom{m}{m-i}.$$ Therefore, $$\binom{2n-2-i}{n-1} = \binom{2n-2-i}{2n-2-i-n+1}=\binom{2n-2-i}{n-1-i}.$$ Consequently, $$\sum_{i=0}^{n-1}\binom{2n-2-i}{n-1} = \sum_{i=0}^{n-1}\binom{2n-2-i}{n-1-i} = \binom{2n-2}{n-1}+\binom{2n-3}{n-2}+\cdots+\binom{n-1}{0}.$$ That is $$\sum_{i=0}^{n-1}\binom{2n-2-i}{n-1} = \sum_{i=0}^{n-1}\binom{n-1+i}{i}.$$

Answer 2

Since you ask for a "transformation", then consider that $$ \bbox[lightyellow] { \eqalign{ & \sum\limits_{0\, \le \,i\, \le \,n - 1} { \left( \matrix{ 2n - 2 - i \cr n - 1 \cr} \right)} = \quad \quad (a.0) \cr & = \sum\limits_{0\, \le \,i\, \le \,n - 1} { \left( \matrix{ 2n - 2 - i \cr n - 1 - i \cr} \right) } = \quad \quad (a.1) \cr & = \sum\limits_{0\, \le \,i\,\left( { \le \,n - 1} \right)} { \left( \matrix{2n - 2 - i \cr n - 1 - i \cr} \right)} = \quad \quad (a.2) \cr & = \sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,n - 1} \right)} { \left( \matrix{ 2n - 2 - i \cr n - 1 - i \cr} \right) \left( \matrix{ i \hfill \cr i \hfill \cr} \right)} = \quad \quad (a.3) \cr & = \left( \matrix{ 2n - 1 \cr n - 1 \cr} \right) \quad \quad (a.4) \cr} }$$ and $$ \bbox[lightyellow] { \eqalign{ & \sum\limits_{0\, \le \,i\, \le \,n - 1} { \left( \matrix{n - 1 + i \cr i \cr} \right) } = \quad \quad (b.0) \cr & = \sum\limits_{\left( {0\, \le } \right)\,i\, \le \,n - 1} { \left( \matrix{ n - 1 + i \cr i \cr} \right) } = \quad \quad (b.1) \cr & = \sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,n - 1} \right)} { \left( \matrix{ n - 1 + i \cr i \cr} \right)\left( \matrix{ n - 1 - i \cr n - 1 - i \cr} \right) } = \quad \quad (b.2) \cr & = \left( \matrix{ 2n - 1 \cr n - 1 \cr} \right) \quad \quad (b.3)\cr} }$$

where:
- a.1) symmetry : we can do that because the upper term is non-negative for $0 \le i \le n-1$;
- a.2) upper bound in brackets to mean that we can remove it since it is implicit in the binomial;
- a.3) lower bound in brackets: it is replaced by the additional binomial;
- a.4) double convolution, we can apply it since the index is free to vary over all the allowed range;
- b.1) lower bound in brackets : it is implicit in the binomial$;
- b.2) upper bound in brackets: replaced by the second binomial;
- b.3) double convolution: the index is free to vary and we can apply it;

Answer 3

A slightly neater way to write what you need to show (letting $N=n-1$) is

$$\color{green}{\sum_{i=0}^{N} \binom{2N-i}{N}} = \color{blue}{\sum_{i=0}^{N} \binom{N+i}{i}}.$$

Using the identity ${m\choose k}\color{red}={m\choose m-k},$

$$\color{blue}{\sum_{i=0}^{N} \binom{N+i}i} \color{red}= \sum_{i=0}^{N} \binom{N+i}{N}=\sum_{M=N}^{2N} \binom{M}{N}=\sum_{M=2N-N}^{2N-0} \binom{M}{N}=\color{green}{\sum_{i=0}^{N} \binom{2N-i}{N}}.$$

Answer 4

We obtain \begin{align*} \color{blue}{\sum_{i=0}^{n-1}\binom{2n-2-i}{n-1}} &=\sum_{i=0}^{n-1}\binom{2n-2-i}{n-1-i}\tag{1}\\ &\,\,\color{blue}{=\sum_{i=0}^{n-1}\binom{n-1+i}{i}}\tag{2} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (2) we change the order of summation $i\to n-1-i$.