# Does this combinatorial identity hold？ [duplicate]

I am trying to prove $$\sum\limits_{k=i+1}^m (-1)^{k-1+i}\binom{m}{k}\binom{k-1}{i}=1,$$ where $$m\geq 1, 1\leq i\leq m-1$$. Actually this is what I induce when I'm trying to calculate what the tangent map of $$\log：\text{PD}_n(\mathbb{R})\rightarrow \text{Sym}_n(\mathbb{R})$$ is， where $$\text{PD}_n(\mathbb{R})$$ is the positive-definite matrix, $$\text{Sym}_n(\mathbb{R})$$ is the symmetric matrix, and $$\log$$ is the inverse map of $$\exp$$. If this identity holds, I can directly write out the formula of tangent map. But I stuck at this step.

• Have you tried specifying small values of $m$ and $i$ first? Jun 5 at 8:50
• It is not hold, $i=1$ is true, but when $i=2$, it gives $3-m$, fails. Jun 5 at 8:56
• These get tricky, but yes, it does seem to hold. Wolfram Alpha Jun 5 at 16:38
• Does this answer your question? How to prove: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$ - found using an Approach0 search. Their expression is basically the same: first multiply by $(-1)^{i+1}$ to get $\sum_{k=i+1}^m(-1)^{k}\binom{m}{k}\binom{k-1}{i}=(-1)^{i+1}$, then replace $m$ with $n$ and $i$ with $m$. Jun 6 at 8:18

We use the coefficient of operator $$[z^i]$$ to denote the coefficient of $$z^i$$ in a series.

We obtain \begin{align*} \color{blue}{\sum_{k=1}^m}&\color{blue}{(-1)^{k-1+i}\binom{m}{k}\binom{k-1}{i}}\tag{1}\\ &=\sum_{k=1}^m(-1)^{k-1+i}\binom{m}{k}[z^i](1+z)^{k-1}\tag{2}\\ &=(-1)^{i-1}[z^i]\frac{1}{1+z}\sum_{k=1}^m\binom{m}{k}(-1)^k(1+z)^k\tag{3}\\ &=(-1)^{i-1}[z^i]\frac{1}{1+z}\left(\left(1-(1+z)\right)^m-1\right)\\ &=(-1)^{i-1}[z^i]\frac{1}{1+z}\left((-z)^m-1\right)\tag{4}\\ &=(-1)^{i}[z^i]\frac{1}{1+z}\tag{5}\\ &\,\,\color{blue}{=1} \end{align*} and the claim follows.

Comment:

• In (1) we start with index $$k=1$$ noting that $$\binom{k-1}{i}=0$$ if $$1\leq k\leq i$$.

• In (2) we use the coefficient of operator $$[z^i]$$.

• in (3) we use the linearity of the coefficient of operator and rearrange the sum to apply the binomial theorem in the next step.

• In (4) we note that $$(-z)^m$$ does not contribute to $$[z^i]$$, since $$i.

• In (5) we use the geometric series expansion $$[z^i]\frac{1}{1+z}=[z^i]\sum_{j=0}^{\infty}(-z)^j=(-1)^i$$.

Hypergeometric functions:

Here is another variation based upon hypergeometric functions. We use the rising factorials notation $$(a)_{k}:=a(a+1)\cdots(a+k-1)$$.

Assuming $$m\geq 1$$ and $$1\leq i\leq m-1$$ we obtain \begin{align*} \color{blue}{\sum_{k=i+1}^m}&\color{blue}{(-1)^{k-1+i}\binom{m}{k}\binom{k-1}{i}}\\ &=\sum_{k=0}^{m-i-1}\underbrace{(-1)^k\binom{m}{k+i+1}\binom{k+i}{i}}_{=:t_k}\\ &=\sum_{k=0}^{m-i-1}t_k=t_0\sum_{k=0}^{m-i-1}\prod_{j=0}^{k-1}\frac{t_{j+1}}{t_j}\\ &=\binom{m}{i+1}\sum_{k=0}^{m-i-1}\prod_{j=0}^{k-1} (-1)^{k+1}\binom{m}{j+i+2}\binom{j+1+i}{i}\\ &\qquad\qquad\qquad\qquad\qquad\cdot(-1)^{-k} \binom{m}{j+i+1}^{-1}\binom{j+i}{i}^{-1}\\ &=\binom{m}{i+1}\sum_{k=0}^{n-j}\prod_{j=0}^{k-1} \frac{\left(j+i+1\right)\left(j+i+1-m\right)}{\left(j+1\right)\left(j+i+2\right)}\\ &=\binom{m}{i+1}\sum_{k=0}^{m-i-1}\frac{(i+1)_k(i+1-m)_k}{(i+2)_k}\,\frac{1}{k!}\\ &=\binom{m}{i+1}{_2F_1}\left(i+1,i+1-m;i+2;1\right)\tag{1}\\ &=\binom{m}{i+1}\,\frac{\Gamma(i+2)\Gamma(m-i)}{\Gamma(1)\Gamma(m+1)}\tag{2}\\ &\,\,\color{blue}{=1} \end{align*} and the claim follows.

Comment:

• In (1) we write the sum as hypergeometric $$_2F_1$$ function evaluated at $$z=1$$ with parameter $$i+1-m$$ a non-positive integer.

• In (2) we recall a theorem from C. F. Gauss [1812] (see e.g. Theorem 2.2.2 in Special Functions by G.E. Andrews, R. Askey and R. Roy) which is \begin{align*} {_2F_1}(a,b;c;1)=\frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)} \end{align*} if $$\Re(c-a-b)>0$$. We derive from (1) $$\Re\left((i+2)-(i+1)-(i+1-m)\right)=m-i>0$$ and get \begin{align*} {_2F_1}(i+1,i+1-m;i+2;1)&=\frac{\Gamma(i+2)\Gamma(m-i)}{\Gamma(1)\Gamma(m+1)}\\ &=\frac{(i+1)!(m-i-1)!}{m!}=\binom{m}{i+1}^{-1} \end{align*}

• FYI, you basically used the first method in your solution above in your answer to the proposed duplicate question. Jun 6 at 8:39
• @JohnOmielan: Ok, I see. Thanks for the hint. Jun 6 at 21:50

Let $$F(m, k, i) = (-1)^{k - 1 + i} {m \choose k} {k - 1 \choose i}$$ be your summand. Note that it satisfies the creative telescoping recurrence

$$(i - m) F(m + 1, k, i) - (i - m) F(m, k, i) = \Delta_k \frac{k(i + 1 - k)}{k - m - 1} F(m, k, i),$$ where $$\Delta_k$$ is the forward shift operator in $$k$$.

If we let $$f(m, i)$$ be your sum and sum this identity from $$k = i + 1$$ to $$k = m + 1$$, then we obtain

$$(i - m) f(m + 1, i) - (i - m) f(m, i) = 0.$$

(The right-hand side is zero because the fraction vanishes at $$k = i + 1$$ and $$F(m, k, i)$$ vanishes for $$k > m$$.) If $$i \neq m$$, it follows that $$f(m + 1, i) = f(m, i)$$. Plugging in, say $$m = i + 1$$, we get

$$f(i + 1, i) = (-1)^{i + 1 - 1 + i} {i + 1 \choose i + 1} {i \choose i} = 1,$$

so $$f(m, i) = 1$$ for all $$m > i$$.

Edit: there was a typo in the question, so this answer is not yet relevant.

For $$i=2$$, $$m=4$$: $$\sum_{k=3}^4 (-1)^{k+1} \binom{4}{k}\binom{k-2}{2} = \binom{4}{3}\binom{1}{2} - \binom{4}{4}\binom{2}{2} = 0 - 1 = -1 \neq 1.$$

• Thanks for your comments. It's a typo that I copied it with a letter wrong. Sorry for the confusion it bring about. Jun 5 at 14:11