2
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

                                              enter image description here

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.