7
$\begingroup$

For $m,n\in\mathbb{N},\;n\geq m$, prove the following:

$$ \tag{i}\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+......+\binom{m}{m} = \binom{n+1}{m+1} $$ $$ \tag{ii}\binom{n}{m}+2\binom{n-1}{m}+3\binom{n-2}{m}+......+(n-m+1)\binom{m}{m} = \binom{n+2}{m+2} $$

My Attempt:

For $(\mathrm{i})$, We can write $\binom{n}{m}$ as the coefficient of $x^m$ in $(1+x)^n$. Thus we can also write $\binom{n-1}{m}$ as the coefficient of $x^m$ in $(1+x)^{n-1}$ and $\binom{n-2}{m}$ as the coefficient of $x^m$ in $(1+x)^{n-2}$. So we have to find the coefficient of $x^m$ in

$$ (1+x)^n+(1+x)^{n-1}+(1+x)^{n-2}+........+(1+x)^{m} $$

Using the formula for the sum of a geometric progression, this sum equals

$$\frac{(1+x)^{n+1}-(1+x)^m}{x}$$

So we now need to find the coefficient of $x^m$ in

$$ \frac{(1+x)^{n+1}-(1+x)^m}{x} $$

or, equivalently, we need to find the coefficient of $x^{m+1}$ in $$ (1+x)^{n+1}-(1+x)^m = \binom{n+1}{m+1} $$

We can use a similar method to solve $(\mathrm{ii})$. Can these questions be solved using combinatorial methods instead?

$\endgroup$
8
$\begingroup$

First problem: We have $n+1$ different doughnuts (labelled $1$ to $n+1$) lined up in a row, and want to choose $m+1$ of them for breakfast. This can be done in $\binom{n+1}{m+1}$ ways. Let us count another way.

Maybe the leftmost doughnut chosen is $1$. There are $\binom{n}{m}$ ways to choose the rest.

Maybe the leftmost doughnut chosen is $2$. There are then $\binom{n-1}{m}$ ways to choose the others.

And so on.

Second Problem: This is done similarly. This time we are choosing $m+2$ doughnuts from $n+2$ doughnuts, labelled $1$ to $n+2$ and lined up in that order.

Look at the leftmost two doughnuts chosen. If the second one is Doughnut $2$, there are $\binom{n}{m}$ ways to choose the rest.

If the second one chosen is Doughnut $3$, there are $2$ ways to choose the first one, and $\binom{n-1}{m}$ ways to choose the rest, for a total of $2\binom{n-1}{2}$.

If the second one chosen is Doughnut $4$, there are $3$ ways to choose the first one, and $\binom{n-2}{m}$ ways to choose the rest, for a total of $3\binom{n-2}{m}$.

And so on.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You've missed one "$" sign. $\endgroup$ – user142971 Aug 21 '15 at 5:01
  • $\begingroup$ @user36790: Thanks, fixed. $\endgroup$ – André Nicolas Aug 21 '15 at 5:08
5
$\begingroup$

Suppose $n \geq m$ and there is a set $S$ of $n + 2$ objects, denoted as $o_1, o_2, \cdots, o_{n+2}$. Your task to sample $m + 2$ objects from $S$. Let $X_i$ denote the # of ways to choose $m + 2$ objects such that the object with second minimum id is $o_i$. Easy to see that $$ X_i = (i-1) \cdot { n + 2 - i \choose m } $$ So we have $$ \sum_{i=2}^{n+2-m} X_i = {n \choose m} + 2\cdot{n-1 \choose m} + \cdots + (n + 1 -m) \cdot {m \choose m} = {n + 2 \choose m + 2} $$


Similar derivation can be applied to (i) with some minor modification. Instead of enumerating the second minimum id, you need to enumerate the minimum id instead.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Maybe a bit late now but here is my answer:

Consider counting the number of possible bit-strings of length $n+i$: $$ \underbrace{111...\overbrace{\textbf{1}}^{i^{\text{th}}\ 1}...111}_{m+i\ 1\text{s}}\ 000...000 $$ So, here $n$ is the number of digits to the right of the $i^\text{th}\ 1$. The number of bit strings is given simply by $\binom{n+i}{m+i}$ where $m$ is the number of $1$s to the right of the $i^{\text{th}}\ 1$.
We may also count bit strings for each possible position of the $i^{\text{th}}\ 1$ (i.e. position $i$, position $i+1$ up to position $i+n-m$) and sum these to give the same result.
When the $i^{\text{th}}\ 1$ is in a position $i+r$ there are $i+r-1$ digits to the left including $i-1$ $1$s and $n-r$ digits to the right including $m$ $1$s.
So if we sum over $r$:
$$\dbinom{n+i}{m+i} = \sum_{r=0}^{n-m} \dbinom{i+r-1}{i-1}\dbinom{n-r}{m} $$ Your two examples are special cases of this identity.
If we put $i=1$ and $i=2$ we have the two required results:
$$\dbinom{n+1}{m+1} = \sum_{r=0}^{n-m} \dbinom{r}{0}\dbinom{n-r}{m} = \sum_{r=0}^{n-m} \dbinom{n-r}{m} = \dbinom{n}{m} + \dbinom{n-1}{m} + ... + \dbinom{m}{m} $$ and
$$\dbinom{n+2}{m+2} = \sum_{r=0}^{n-m} \dbinom{r+1}{1}\dbinom{n-r}{m} = \sum_{r=0}^{n-m} \left(r+1\right)\dbinom{n-r}{m} = 1\dbinom{n}{m} + 2\dbinom{n-1}{m} + ... + \left(n-m+1\right)\dbinom{m}{m} $$

| cite | improve this answer | |
$\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.