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

Question

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)

Answer 1

\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}

Answer 2

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

Answer 3

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.