# Is there a simple proof of the following binomial Identity (part 2)?

This is a related question to the one I posted on MO earlier:

Is there a simple proof of the following Identity for $\sum_{k=m-1}^l(-1)^{k+m}\frac{k+2}{k+1}{\binom l k}\binom{k+1}m$?

It arose in the same context: the degeneracy of umbilic points on Weingarten surfaces.

For all $l,m\in{\mathbb N}$ with $l\geq m\geq0$ the following identities appear to hold: \begin{eqnarray} &(1-(2m+1)(m+1)){\textstyle{{l+1 \choose m}}}\nonumber\\ +\sum\limits_{k=m+1}^{l+1}&(-1)^{\scriptstyle{{k+m}}}{\textstyle{{l+1 \choose k}}}\left[(1-(2k+1)(m+2)){\textstyle{\frac{2m+2}{2k+1}{k \choose m+1}}}+(1-(2k+1)(m+1)){\textstyle{\frac{2m+1}{2k+1}{k \choose m}}}\right]\nonumber\\ &= \left\{\begin{array}{ccl} 0&if& l>m\\ 2(l+1)(l+2) &if& l=m \end{array}. \right.\nonumber \end{eqnarray}

Obviously the $l=m$ case is trivial (I include it for completeness). So, any suggestions for a proof of this?

• First step: The beauty inside the square brackets simplifies to $\left(m-4k-2km\right)\dbinom{k}{m}$. The second step could be observing that $\dbinom{l}{k}\dbinom{k}{m} = \dbinom{l}{m}\dbinom{l-m}{k-m}$, and of course the $\dbinom{l}{m}$ can be taken out of the sum. After that, I believe you end up with the $l-m$-th finite difference of a degree-$1$ polynomial in $k$. Aug 6, 2017 at 12:50
• That said, I suspect there are typos in the statement. The sum goes all the way up to $l+1$, but the $\dbinom{l}{k}$ kills the $k=l+1$ addend, which doesn't smell of intent to me. Aug 6, 2017 at 12:55
• @darij grinberg - correct and now corrected! Aug 6, 2017 at 13:48
• I don't think you need anything more than Darij's first step. This gives the $(l+1)$th (or is it $(l+1)$st?) difference of a polynomial in $k$ of degree $m+1$ Aug 7, 2017 at 19:20

Following the hint @darijgrinberg stated in the comment section with respect to the beauty inside the square brackets we focus on the sum and

Comment:

• In (1) we use @darijgrinbergs simplified bracketed beauty.

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

• In (3) we shift the index to start with $k=1$.

• In (4) we split the sum and do some simplifications regarding $(1-1)^{l+1-m}$ using Iverson brackets.

• In (5) and (6) we use the binomial identity $$\binom{p+1}{q+1}=\frac{p+1}{q+1}\binom{p}{q}$$ and we shift the index to start with $k=0$.

• In (7) we do some final simplifications and adaptions to better see the relationship with OPs identity.

• The context in which this arose is now in a paper on the arxiv: arxiv.org/abs/1709.00580 Sep 5, 2017 at 17:17

Let $l$ and $m$ be two integers such that $l\geq m\geq0$. You want me to prove the identity \begin{align} & \left( 1-\left( 2m+1\right) \left( m+1\right) \right) \dbinom{l+1} {m}+\sum_{k=m+1}^{l+1}\left( -1\right) ^{k+m}\dbinom{l+1}{k}Q\left( k,m\right) \nonumber\\ & = \begin{cases} 0, & \text{if }l>m;\\ 2\left( l+1\right) \left( l+2\right) , & \text{if }l=m \end{cases} ,\tag{1}\label{g-pf.1} \end{align} where \begin{align*} Q\left( k,m\right) & =\left( 1-\left( 2k+1\right) \left( m+2\right) \right) \dfrac{2m+2}{2k+1}\dbinom{k}{m+1}\\ & +\left( 1-\left( 2k+1\right) \left( m+1\right) \right) \dfrac {2m+1}{2k+1}\dbinom{k}{m}. \end{align*}

Set $x=-2m-4$ and $y=-2m^{2}-3m$. Then, $y=1-\left( 2m+1\right) \left( m+1\right)$.

Every nonnegative integer $k$ satisfies $\dbinom{k}{m+1}=\dfrac{k-m} {m+1}\dbinom{k}{m}$ (by straightforward computation), and therefore the definition of $Q\left( k,m\right)$ rewrites as \begin{align} Q\left( k,m\right) & =\left( 1-\left( 2k+1\right) \left( m+2\right) \right) \dfrac{2m+2}{2k+1}\cdot\dfrac{k-m}{m+1}\dbinom{k}{m}\nonumber\\ & +\left( 1-\left( 2k+1\right) \left( m+1\right) \right) \dfrac {2m+1}{2k+1}\dbinom{k}{m}\nonumber\\ & =\left( m-4k-2km\right) \dbinom{k}{m}\tag{3}\label{g-pf.3} \end{align} (after some straightforward computation).

On the other hand, it is known that any three integers $a$, $b$ and $c$ satisfying $b\geq c$ satisfy $$\dbinom{a}{b}\dbinom{b}{c}=\dbinom{a}{c}\dbinom{a-c}{b-c}\tag{5}\label{g-pf.5}$$ (this is the so-called trinomial revision formula, in Knuth's terminology). Now, \begin{align} & \sum_{k=m+1}^{l+1}\left( -1\right) ^{k+m}\dbinom{l+1}{k} \underbrace{Q\left( k,m\right) }_{\substack{=\left( m-4k-2km\right) \dbinom{k}{m}\\\text{(by \eqref{g-pf.3})}}}\nonumber\\ & =\sum_{k=m+1}^{l+1}\left( -1\right) ^{k+m}\dbinom{l+1}{k}\left( m-4k-2km\right) \dbinom{k}{m}\nonumber\\ & =\sum_{k=m+1}^{l+1}\left( -1\right) ^{k+m}\left( m-4k-2km\right) \underbrace{\dbinom{l+1}{k}\dbinom{k}{m}}_{\substack{=\dbinom{l+1}{m} \dbinom{l+1-m}{k-m}\\\text{(by \eqref{g-pf.5}, applied to }a=l+1\text{, }b=k\text{ and }c=m\text{)}}}\nonumber\\ & =\sum_{k=m+1}^{l+1}\left( -1\right) ^{k+m}\left( m-4k-2km\right) \dbinom{l+1}{m}\dbinom{l+1-m}{k-m}\nonumber\\ & =\sum_{k=1}^{l+1-m}\underbrace{\left( -1\right) ^{k+m+m}}_{=\left( -1\right) ^{k}}\underbrace{\left( m-4\left( k+m\right) -2\left( k+m\right) m\right) }_{\substack{=xk+y\\\text{(by straightforward computation)}}}\dbinom{l+1}{m}\dbinom{l+1-m}{k}\nonumber\\ & \ \ \ \ \ \ \ \ \ \ \left( \text{here, we have substituted }k+m\text{ for }k\text{ in the sum}\right) \nonumber\\ & =\sum_{k=1}^{l+1-m}\left( -1\right) ^{k}\left( xk+y\right) \dbinom {l+1}{m}\dbinom{l+1-m}{k}.\tag{7}\label{g-pf.7} \end{align} But \begin{align} & \dbinom{l+1}{m}\sum_{k=0}^{l+1-m}\left( -1\right) ^{k}\left( xk+y\right) \dbinom{l+1-m}{k}\nonumber\\ & =\sum_{k=0}^{l+1-m}\left( -1\right) ^{k}\left( xk+y\right) \dbinom {l+1}{m}\dbinom{l+1-m}{k}\nonumber\\ & =\underbrace{\left( -1\right) ^{0}}_{=1}\underbrace{\left( x\cdot 0+y\right) }_{\substack{=y\\=1-\left( 2m+1\right) \left( m+1\right) }}\dbinom{l+1}{m}\underbrace{\dbinom{l+1-m}{0}}_{=1}\nonumber\\ & \ \ \ \ \ \ \ \ \ \ +\underbrace{\sum_{k=1}^{l+1-m}\left( -1\right) ^{k}\left( xk+y\right) \dbinom{l+1}{m}\dbinom{l+1-m}{k}}_{\substack{=\sum _{k=m+1}^{l+1}\left( -1\right) ^{k+m}\dbinom{l+1}{k}Q\left( k,m\right) \\\text{(by \eqref{g-pf.7})}}}\nonumber\\ & =\left( 1-\left( 2m+1\right) \left( m+1\right) \right) \dbinom{l+1} {m}+\sum_{k=m+1}^{l+1}\left( -1\right) ^{k+m}\dbinom{l+1}{k}Q\left( k,m\right) .\tag{11}\label{g-pf.11} \end{align} Thus, the left-hand side of the equality \eqref{g-pf.1} is the left-hand side of \eqref{g-pf.11}.

But it is well-known (and follows, e.g., from the binomial formula) that $$\sum_{k=0}^{N}\left( -1\right) ^{k}\dbinom{N}{k}= \begin{cases} 1, & \text{if }N=0;\\ 0, & \text{if }N>0 \end{cases} \tag{12}\label{g-pf.12}$$ for every nonnegative integer $N$. Hence, for every positive integer $N$, we have $$\sum_{k=0}^{N}\left( -1\right) ^{k}\dbinom{N}{k}= \begin{cases} 1, & \text{if }N=0;\\ 0, & \text{if }N>0 \end{cases} =0\tag{13}\label{g-pf.13}$$ (since $N>0$). Now, for every positive integer $N$, we have \begin{align} \sum_{k=0}^{N}\left( -1\right) ^{k}k\dbinom{N}{k} & =\underbrace{\left( -1\right) ^{0}0\dbinom{N}{0}}_{=0}+\sum_{k=1}^{N}\left( -1\right) ^{k}\underbrace{k\dbinom{N}{k}}_{=N\dbinom{N-1}{k-1}}\nonumber\\ & =\sum_{k=1}^{N}\left( -1\right) ^{k}N\dbinom{N-1}{k-1}=N\sum_{k=1} ^{N}\left( -1\right) ^{k}\dbinom{N-1}{k-1}\nonumber\\ & =N\sum_{k=0}^{N-1}\underbrace{\left( -1\right) ^{k+1}}_{=-\left( -1\right) ^{k}}\dbinom{N-1}{k}\nonumber\\ & \ \ \ \ \ \ \ \ \ \ \left( \text{here, we have substituted }k+1\text{ for }k\text{ in the sum}\right) \nonumber\\ & =-N\underbrace{\sum_{k=0}^{N-1}\left( -1\right) ^{k}\dbinom{N-1}{k} }_{\substack{= \begin{cases} 1, & \text{if }N-1=0;\\ 0, & \text{if }N-1>0 \end{cases} \\\text{(by \eqref{g-pf.12}, applied to }N-1\text{ instead of }N\text{)}}}=-N \begin{cases} 1, & \text{if }N-1=0;\\ 0, & \text{if }N-1>0 \end{cases} \nonumber\\ & = \begin{cases} -N, & \text{if }N-1=0;\\ 0, & \text{if }N-1>0 \end{cases} = \begin{cases} -N, & \text{if }N=1;\\ 0, & \text{if }N>1 \end{cases} \nonumber\\ & = \begin{cases} -1, & \text{if }N=1;\\ 0, & \text{if }N>1 \end{cases} \tag{15}\label{g-pf.15} \end{align} (since $-N=-1$ in the case when $N=1$). Hence, for every positive integer $N$, we have \begin{align*} \sum_{k=0}^{N+1}\left( -1\right) ^{k}\left( xk+y\right) \dbinom{N}{k} & =x\underbrace{\sum_{k=0}^{N+1}\left( -1\right) ^{k}k\dbinom{N}{k} }_{\substack{= \begin{cases} -1, & \text{if }N=1;\\ 0, & \text{if }N>1 \end{cases} \\\text{(by \eqref{g-pf.15})}}}+y\underbrace{\sum_{k=0}^{N+1}\left( -1\right) ^{k}\dbinom{N}{k}}_{\substack{=0\\\text{(by \eqref{g-pf.13})}}}\\ & =x \begin{cases} -1, & \text{if }N=1;\\ 0, & \text{if }N>1 \end{cases} +y0= \begin{cases} -x, & \text{if }N=1;\\ 0, & \text{if }N>1 \end{cases} . \end{align*} Applying this to $N=l+1-m$ (which is a positive integer since $l+1>l\geq m$), we obtain \begin{align*} \sum_{k=0}^{l+1-m}\left( -1\right) ^{k}\left( xk+y\right) \dbinom {l+1-m}{k} & = \begin{cases} -x, & \text{if }l+1-m=1;\\ 0, & \text{if }l+1-m>1 \end{cases} \\ & = \begin{cases} -x, & \text{if }l=m;\\ 0, & \text{if }l>m \end{cases} . \end{align*} Now, \eqref{g-pf.11} yields \begin{align*} & \left( 1-\left( 2m+1\right) \left( m+1\right) \right) \dbinom{l+1} {m}+\sum_{k=m+1}^{l+1}\left( -1\right) ^{k+m}\dbinom{l+1}{k}Q\left( k,m\right) \\ & =\dbinom{l+1}{m}\underbrace{\sum_{k=0}^{l+1-m}\left( -1\right) ^{k}\left( xk+y\right) \dbinom{l+1-m}{k}}_{= \begin{cases} -x, & \text{if }l=m;\\ 0, & \text{if }l>m \end{cases} }\\ & =\dbinom{l+1}{m} \begin{cases} -x, & \text{if }l=m;\\ 0, & \text{if }l>m \end{cases} = \begin{cases} -\dbinom{l+1}{m}x, & \text{if }l=m;\\ 0, & \text{if }l>m \end{cases} \\ & = \begin{cases} 0, & \text{if }l>m;\\ -\dbinom{l+1}{m}x, & \text{if }l=m \end{cases} = \begin{cases} 0, & \text{if }l>m;\\ 2\left( l+1\right) \left( l+2\right) , & \text{if }l=m \end{cases} \end{align*} (because $-\dbinom{l+1}{m}x=2\left( l+1\right) \left( l+2\right)$ in the case when $l=m$ (this follows by trivial computations)). This proves \eqref{g-pf.1}.