Why does this relation of binomials hold?

Question

Why does $\sum_{m=n}^N m\binom {m-1}{n-1}=\sum_{m=n}^N n \binom mn=n \binom{N+1}{n+1}$ is true? Is there some special formula for it?

Answer 1

The first equality is due to the equality in @OlivierOloa's answer. The second one is a bit trick to obtain.

1. Change $\binom nn$ to $\binom {n+1}{n+1}$.
2. Group the first two term.
3. Apply the equality $\binom nk + \binom n{k+1} = \binom {n+1}{k+1}$ to condense the leftmost two terms into one.
4. Repeat (3) until only one term left.

\begin{align} &\binom nn + \binom {n+1}n + \binom {n+2}n + \dots + \binom Nn \\ &= \left[\binom {n+1}{n+1} + \binom {n+1}n \right] + \binom {n+2}n + \dots + \binom Nn \\ &= \left[\binom {n+2}{n+1} + \binom {n+2}n\right] + \dots + \binom Nn \\ &= \cdots \\ &= \binom{N+1}{n+1} \end{align}

Answer 2

Is there some special formula for it?

One has $$ m\binom {m-1}{n-1}=m\frac{(m-1)!}{(n-1)!(m-1-n+1)!}=n\frac{m!}{n!(m-n)!}=n \binom mn. $$

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{m = n}^{N}m{m - 1 \choose n - 1} & = \sum_{m = n}^{N}m\bracks{z^{n - 1}}\pars{1 + z}^{m - 1} = \bracks{z^{n - 1}}\sum_{m = n}^{N}m\pars{1 + z}^{m - 1} \\[5mm] & = \bracks{z^{n - 1}}\partiald{}{z}\sum_{m = n}^{N}\pars{1 + z}^{m} = \bracks{z^{n - 1}}\partiald{}{z}\bracks{% \pars{1 + z}^{n}\,{\pars{1 + z}^{N - n + 1} - 1 \over \pars{1 + z} - 1}} \\[5mm] & = \bracks{z^{n - 1}}\partiald{}{z}\bracks{% \pars{1 + z}^{N + 1} - \pars{1 + z}^{n} \over z} \\[5mm] & = \bracks{z^{n - 1}}\partiald{}{z}\bracks{% \sum_{k = 0}^{N + 1}{N + 1 \choose k}z^{k - 1} - \sum_{k = 0}^{n}{n \choose k}z^{k - 1}} \\[5mm] & = \bracks{z^{n - 1}}\bracks{% \sum_{k = 0}^{N + 1}{N + 1 \choose k}\pars{k - 1}z^{k - 2} - \sum_{k = 0}^{n}{n \choose k}\pars{k - 1}z^{k - 2}} \\[5mm] & = \sum_{k = 0}^{N + 1}{N + 1 \choose k}\pars{k - 1}\delta_{n - 1,k - 2} - \sum_{k = 0}^{n}{n \choose k}\pars{k - 1}\delta_{n - 1,k - 2} \\[5mm] & = {N + 1 \choose n + 1}n\bracks{0 \leq n + 1 \leq N + 1}\ -\ \underbrace{{n \choose n + 1}}_{\ds{=\ 0}}\ n\bracks{0 \leq n + 1 \leq N + 1} \\[5mm] & = \bbx{n{N + 1 \choose n + 1}} \end{align}

Answer 4

Combinatorially: $$m\binom {m-1}{n-1}=\underbrace{{m\choose 1}\binom {m-1}{n-1}}_{LHS}=\underbrace{\binom mn {n\choose 1}}_{RHS}=n\binom mn.$$ LHS: In a group of $m$ students, we select $1$ group representative. From the remaining $m-1$ students we select $n-1$ assistants. Note that in total $n$ students out of $m$ were selected.

RHS: In the same group of $m$ students, we select $n$ students ($1$ to be a group representative and the rest $n-1$ to be assistants). From these $n$ students we select $1$ group representative.