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)
Best Answer
\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}