Evaluating summation involving combinations

Question

Question:

If $\sum_{r=m}^{n} {^r}C_m=^{n+1}C_{m+1}$, evaluate: $$\sum_{r=m}^n (n-r+1)\cdot^rC_m$$

My attempt:

I know we can split the brackets into three parts and easily evaluate summation of $n\cdot^rC_m$ and $^rC_m$ using the given condition. However, I do not know how to deal with the $(-1)\cdot r\cdot^rC_m$ that comes in the expansion.

I know about many summation methods (break $r$ into $(r+1)-1$ and others), and many identities that help solve such expressions, but they don't match here, and hence I am unable to proceed any further.

Can anyone please give some hints? (include the identity you're using using, if any)

Answer 1

First Identity

$$\bbox[#FFA,15px,border: solid black 1px]{\sum_{r=m}^{n}\binom{r}{m}=\binom{n+1}{m+1}\qquad(1)}$$

Example

Count bit strings with $n+1=8$ digits and $m+1=3$ "1"s by counting mutually exclusive cases where the first "1" is in different positions.

We are counting arrangements of bit strings either side of the red "1" and multiplying in each case.

$$\color{red}{1}1100000\quad\longrightarrow\, \text{arrangements}=\binom{0}{0}\binom{7}{2}$$ $$0\color{red}{1}110000\quad\longrightarrow\, \text{arrangements}=\binom{1}{1}\binom{6}{2}$$ $$00\color{red}{1}11000\quad\longrightarrow\, \text{arrangements}=\binom{2}{2}\binom{5}{2}$$ $$000\color{red}{1}1100\quad\longrightarrow\, \text{arrangements}=\binom{3}{3}\binom{4}{2}$$ $$0000\color{red}{1}110\quad\longrightarrow\, \text{arrangements}=\binom{4}{4}\binom{3}{2}$$ $$00000\color{red}{1}11\quad\longrightarrow \text{arrangements}=\binom{5}{5}\binom{2}{2}$$

add up all these 6 cases to give

$$\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2}+\binom{6}{2}+\binom{7}{2}=35$$

but this must add up to the total arrangements

$$\binom{8}{3}=35$$

Second identity

$$\bbox[#FFA,15px,border: solid black 1px]{\sum_{r=m}^{n}\binom{n-r+1}{1}\binom{r}{m}=\binom{n+2}{m+2}\qquad(2)}$$

Note: $\binom{n-r+1}{1}=n-r+1$.

Example

Count bit strings with $n+2=8$ digits and $m+2=4$ "1"s by counting mutually exclusive cases where the second "1" is in different positions.

We are, again, counting arrangements of bit strings either side of the red "1" and muliplying in each case.

$$1\color{red}{1}110000\quad\longrightarrow\, \text{arrangements}=\binom{1}{1}\binom{6}{2}$$ $$10\color{red}{1}11000\quad\longrightarrow\, \text{arrangements}=\binom{2}{1}\binom{5}{2}$$ $$100\color{red}{1}1100\quad\longrightarrow\, \text{arrangements}=\binom{3}{1}\binom{4}{2}$$ $$1000\color{red}{1}110\quad\longrightarrow\, \text{arrangements}=\binom{4}{1}\binom{3}{2}$$ $$10000\color{red}{1}11\quad\longrightarrow\, \text{arrangements}=\binom{5}{1}\binom{2}{2}$$

add up all these 5 cases to give

$$\binom{5}{1}\binom{2}{2}+\binom{4}{1}\binom{3}{2}+\binom{3}{1}\binom{4}{2}+\binom{2}{1}\binom{5}{2}+\binom{1}{1}\binom{6}{2}=70$$

but this must add up to the total arrangements

$$\binom{8}{4}=70$$

as required.

Answer 2

Given the form of the question, the desired answer is probably not a combinatorial argument. Consider instead $$\begin{eqnarray} \sum_{r=m}^n (n - r + 1) \binom{r}{m} & = & \left((n+1) \sum_{r=m}^n \binom{r}{m} \right) - \sum_{r=m}^n r \binom{r}{m} \\ & = & (n+1)\binom{n+1}{m+1} - \sum_{r=m}^n r \binom{r}{m} \\ \end{eqnarray}$$ by the given identity. Now we presumably want to get the right hand side into a suitable form. The obvious way is to try eliminating the $r$ inside the sum by turning it into a series of sums of binomial coefficients. I.e. (with all the intermediate steps) $$\begin{eqnarray} \sum_{r=m}^n r \binom{r}{m} & = & \left(m \sum_{r=m}^n \binom{r}{m}\right) + \left(\sum_{r=m}^n (r-m) \binom{r}{m}\right) \\ & = & m \binom{n+1}{m+1} + \left( \binom{m+1}{m} + 2\binom{m+2}{m} + \ldots + (n-m)\binom{n}{m} \right) \\ & = & m \binom{n+1}{m+1} + \sum_{j=m+1}^n \binom{j}{m} + \ldots \sum_{j=n}^n \binom{j}{m} \\ & = & m \binom{n+1}{m+1} + \sum_{i=m+1}^n \sum_{j=i}^n \binom{j}{m} \\ & = & m \binom{n+1}{m+1} + \sum_{i=m+1}^n \binom{i+1}{m+1} \\ & = & m \binom{n+1}{m+1} + \sum_{k=m+2}^{n+1} \binom{k}{m+1} \\ & = & m \binom{n+1}{m+1} - \binom{m+1}{m+1} + \sum_{k=m+1}^{n+1} \binom{k}{m+1} \\ & = & m \binom{n+1}{m+1} - 1 + \binom{n+2}{m+2} \end{eqnarray}$$ where $k = i+1$ is a change of variables.

Thus just using the given identity (ok, and $\binom{m+1}{m+1} = 1$) we get $$\sum_{r=m}^n (n - r + 1) \binom{r}{m} = (n-m+1)\binom{n+1}{m+1} - \binom{n+2}{m+2} + 1$$ which can no doubt be simplified.