# Evaluating summation involving combinations

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)

• The first identity can be found by considering counting binary strings of $n+1$ digits and $m+1$ 1s. The leftmost 1 can be in the first position in $\binom{n}{m}$ ways, the second position in $\binom{n−1}{m}$ ways etc, summing these gives total arrangements $\binom{n+1}{m+1}$. The second one is much the same as we may argue using the positions of the next-to-leftmost 1 of a binary string length $n+2$ with $m+2$ 1s. It may be in position 2 in $\binom{1}{1}\binom{n}{m}$ ways, in position 3 in $\binom{2}{1}\binom{n−1}{m}$ ways etc, sum these to give $\binom{n+2}{m+2}$. Commented Mar 7, 2017 at 15:48
• @N.Shales could you please write that as an answer, and illustrate with an example or two? Thanks! Commented Mar 8, 2017 at 2:35

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.

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.