How to prove that $n \choose r$ = $\frac{n+1-r}{r}$ $n \choose r-1$ without using the factorial expansion of $n \choose r$?

Question

How to prove that $n \choose r$ = $\frac{n+1-r}{r}$ $n \choose r-1$ without using the factorial expansion of $n \choose r$.

Answer 1

The left-hand-side clearly counts the number of ways to choose $r$ objects out of $n$ total.

The right-hand-side counts the same, but its logic is the following:

• Pick $r-1$ objects first.

• From the remaining $n-(r-1)$ objects, pick one of them to fill the remaining empty spot.

• Recognize that for each choice of $r$ objects, this method has counted each a total of $r$ times, so divide by $r$ to account for the symmetry of the problem.

This gives a total of $\binom{n}{r-1}(n-(r-1))\cdot\frac{1}{r}=\frac{n+1-r}{r}\binom{n}{r-1}$ ways of selecting $r$ objects out of $n$ total.

By fundamental principles, if two expressions correctly count the number of outcomes of the same scenario, then they must be equal.

Answer 2

It's easier to see it if you write it as:

$$\binom{n}{r}r=\binom{n}{r-1}(n+1-r)$$

The left side counts the number of ways to select $r$ elements, then select one of those $r$.

The right side is the number of ways to select $r-1$ elements, and then select one more element from the $n-(r-1)=n-r+1$ remaining elements.

---

You can prove the theorem inductively on $n$, using $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$, the Pascal triangle identity.

I'll skip the case $n=1$.

If true for $n$, then for $r\geq 1$ we have:

$$\begin{align}r\binom{n+1}{r} &=r\binom{n}{r-1} + r\binom{n}{r}\\ &= r\binom{n}{r-1}+(n-r+1)\binom{n}{r-1}\tag{*}\\ &= (n+1)\binom{n}{r-1} \end{align}$$

Where the substitution $(*)$ is allowed by the induction hypothesis.

On the other hand, if $r>1$, then:

$$\begin{align}(n+1-r+1)\binom{n+1}{r-1} &=(n+2-r)\binom{n}{r-1}+(n+2-r)\binom{n}{r-2}\\ &=(n+2-r)\binom{n}{r-1}+(r-1)\binom{n}{r-1}\tag{*}\\ &=(n+1)\binom{n}{r-1} \end{align}$$

where again, the substitution is allowed by the induction hypothesis.

So the two values are equal. You have to deal with the care where $r=1$ separately.

So $$r\binom{n+1}{r}=((n+1)-r+1)\binom{n+1}{r-1}$$

and the induction is done.

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#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}$

One possible approach is the introduction of a Generating Function 'technique'. Essentially, it just involves the identity $\ds{\left.\sum_{r = 1}^{\infty}{n \choose r}z^{r} \,\right\vert_{\ \verts{z}\ <\ 1}\ =\ \pars{1 + z}^{n} - 1}$. Hereafter, I'll develop this approach:

\begin{align} &\sum_{r = 1}^{\infty}\color{#f00}{{n + 1 - r \over r}{n \choose r - 1}}z^{r} = \sum_{r = 0}^{\infty}{n - r \over r + 1}{n \choose r}z^{r + 1} = \pars{n + 1}z\sum_{r = 0}^{\infty}{n \choose r}{z^{r} \over r + 1} - z\sum_{r = 0}^{\infty}{n \choose r}z^{r} \\[5mm] = &\ \pars{n + 1}z\sum_{r = 0}^{\infty}{n \choose r}z^{r}\int_{0}^{1}t^{r}\,\dd t - z\pars{1 + z}^{n} \\[5mm] = &\ \pars{n + 1}z\int_{0}^{1}\pars{1 + zt}^{n}\,\dd t - \pars{1 + z}^{n + 1} + \pars{1 + z}^{n} \\[5mm] & = \pars{n + 1}z\,{\pars{1 + z}^{n + 1} - 1 \over \pars{n + 1}z} - \pars{1 + z}^{n + 1} + \pars{1 + z}^{n} = \pars{1 + z}^{n} - 1 = \sum_{r = 1}^{\infty}\color{#f00}{n \choose r}z^{r} \end{align}

Answer 4

Here is an answer based upon the two binomial identities \begin{align*} \binom{n}{r}&=\binom{n}{n-r}\tag{1}\\ \binom{n}{r}&=\binom{n-1}{r-1}\frac{n}{r}\tag{2} \end{align*}

We start with the right-hand side and obtain \begin{align*} \frac{n+1-r}{r}\binom{n}{r-1}&=\frac{n+1-r}{r}\binom{n}{n+1-r}\qquad &\rightarrow (1)\\ &=\frac{n+1-r}{r}\cdot \frac{n}{n+1-r}\binom{n-1}{n-r}\qquad &\rightarrow (2)\\ &=\frac{n}{r}\binom{n-1}{n-r}\\ &=\frac{n}{r}\binom{n-1}{r-1}&\qquad\rightarrow (1)\\ &=\binom{n}{r}&\quad\rightarrow (2) \end{align*}

Answer 5

Consider the bipartite graph where vertices on the left side are the $k$-sets and vertices on the other are $(k+1)$-sets and we connect two if one contains the other.

Since vertices on the left side have degree $n-k$ and vertices on the right have degree $k+1$ we get the desired equality when counting the number of edges.

Answer 6

• $\dbinom nr\dbinom r 1$ counts all the distinct ways to select $r$ from $n$ items and then $1$ from those $r$. Thus produce sets of size $r-1$, $1$, and $n-r$ items from a set of $n$ items.

• $\dbinom{n}{r-1}\dbinom {n-r+1}1$ all the distinct ways to select $r-1$ from $n$ items and then $1$ from the remaining $n-r+1$ items. Thus produce sets of size $1$, $r-1$, and $n-r$ items from a set of $n$ items.

• These counts must be equal.