Does this combinatorial identity hold？ [duplicate]

Question

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.

Answer 1

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<m$.

• 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*}

Answer 2

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$.

Answer 3

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. $$