# Proof of $\sum_{k=1}^{i} \binom{n-k}{n-i} = \frac{n \cdot \binom{n-1}{n-i}}{n+1-i}$

I'm trying to prove the following identity:

For each $$i \in \mathbb{N}, \sum_{k=1}^{i} \binom{n-k}{n-i} = \frac{n \cdot \binom{n-1}{n-i}}{n+1-i}$$

My attempt: I've tried to prove that $$(n+1-i) \cdot \sum_{k=1}^{i} \binom{n-k}{n-i} = n \cdot \binom{n-1}{n-i}$$, and I've noticed that:

$$\sum_{k=1}^{i} \binom{n-k}{n-i} = \sum_{k=1}^{i} \binom{n-k}{i-k}$$

$$n \cdot \binom{n-1}{n-i} = n \cdot \binom{n-1}{i-1}$$

I don't want to use induction, so I've tried proving it combinatorically: The right-hand side counts the number of ways of constructing a subset of $$i$$ elements (from $$n$$ elements), with a "special" element.

However, I cannot interpret the left-hand side similarily.

Is there a way of interpreting it, or proving it in a different way? (For example, using the Binomial theorem)

\begin{align} \sum_{k=1}^i\binom{n-k}{n-i} &= \sum_{k=1}^i\frac{(n-k)!}{(n+1-i)!(i-k-1)!}\left(\frac{n+1-i}{i-k}\right)\\ &=\sum_{k=1}^i\frac{(n-k)!}{(n+1-i)!(i-k-1)!}\left(\frac{n+1-k}{i-k}-1\right)\\ &= \sum_{k=1}^i\binom{n+1-k}{n+1-i}-\binom{n-k}{n+1-i}\\ &=\binom{n}{n+1-i}= \frac{n(n-1)!}{(i-1)!(n-i)!(n+1-i)} \\ &= \frac{n\binom{n-1}{n-i}}{n+1-i} \end{align}

Here is a combinatorial proof using lattice paths. At first we note the right hand side can be written as \begin{align*} \frac{n \cdot \binom{n-1}{n-i}}{n+1-i}=\binom{n}{n+1-i} \end{align*} We therefore want to show \begin{align*} \binom{n}{n+1-i}&=\sum_{k=1}^i\binom{n-k}{n-i}\\ &=\binom{n-1}{n-i}+\binom{n-2}{n-i}+\cdots+\binom{n-i}{n-i}\tag{1} \end{align*}

We consider the lattice paths of length $$n$$ from $$(0,0)$$ to $$(n+1-i,i-1)$$ consisting of $$(1,0)$$-steps and $$(0,1)$$-steps only. The number of these paths is $$\binom{n}{n+1-i}$$ since we have to choose precisely $$n+1-i$$ $$(1,0)$$-steps out of $$n$$ steps.

We fix a vertical line going through $$(n-i,0)$$. Each path from $$(0,0)$$ to $$(n+1-i,i-1)$$ will cross the line at some point $$(n-i,i-k)$$ with $$1\leq k\leq i$$ and the number of these paths is $$\binom{n-k}{i-k}$$.

We can so partition all valid paths by taking paths crossing the line at a specific height $$i-k$$, followed by a horizontal step to $$(n+1-i,i-k)$$ and $$k-1$$ vertical steps to $$(n+1-i,i-1)$$.

We conclude the binomial identity (1) is valid.

Another Proof: Let $$[x^j]$$ denote the co-efficient of $$x^j$$ in the following expression. The the sum $$S=\sum_{k=1}^i {n-k \choose n-i}=[x^{n-i}]~~\left ( \sum_{k=1}^{i} (1+x)^{n-k}\right) =[x^{n-i}]~~ (1+x)^{n-1} \left( \sum_{k=1}^{i} (1+x)^{-(k-1)}\right)$$ $$\Rightarrow S= [x^{n-i}]~~ (1+x)^{n-1} \left(\frac{ (1+x)^{-i}-1}{(1+x)^{-1}-1} \right) = [x^{n-i+1}]~~ \left ((1+x)^n-(1+x)^{n-i} \right)={n \choose n-i+1}=\frac {n}{n-i+1} {n-1 \choose n-i}.$$