Show ${156 \choose 87} + {156 \choose 86} = {157 \choose 87}$

Question

How can we show the following equality?

$${156 \choose 87} + {156 \choose 86} = {157 \choose 87}$$

Answer 1

Algebraic proof:

$\binom{n}{k+1}+\binom{n}{k}=\frac{n!}{(k+1)!(n-k-1)!}+\frac{n!}{k!(n-k)!}=\frac{n!(n-k)}{(k+1)!(n-k)!}+\frac{n!(k+1)}{(k+1)!(n-k)!}=\frac{(n+1)!}{(k+1)!(n-k)!}=\binom{n+1}{k+1}$

Combinatorial proof:

If we want to choose $(k+1)$ objects out of $(n+1)$ objects, we either choose the first one and then choose $k$ more from the remaining $n$ objects or not choose the first one and then choose all $(k+1)$ from the remaining $n$ objects.

Answer 2

In general, $$\dbinom{n}r + \dbinom{n}{r-1} = \dbinom{n+1}r$$ There are many ways to prove this, a simple way is just to manipulate the left hand side algebraically to obtain the right hand side i.e. \begin{align} \dbinom{n}r + \dbinom{n}{r-1} & = \dfrac{n!}{r! (n-r)!} + \dfrac{n!}{(r-1)! (n-r+1)!}\\ & = \dfrac{n!}{r! (n+1-r)!} \left(n+1-r + r \right)\\ & = \dfrac{n!}{r! (n+1-r)!} \left(n+1 \right)\\ & = \dfrac{(n+1)!}{r! (n+1-r)!}\\ & = \dbinom{n+1}r \end{align} Take $n=156$ and $r=87$ to get what you want.

Answer 3

Hint: Given a set of $157$ objects and you are choosing $87$ items out of it, you can either take the first element or not take it. How many ways are there to pick the $87$ objects in each case?

Answer 4

I think this is the best way to do it. Using Wolfram Alpha, we see that

$$\begin{align} \binom{156}{87} &= 2071356239566075202805184663760798068902414000\\[12pt] \binom{156}{86} &= 2574399897746407752057872367816991885635857400\\[12pt] \binom{157}{87} &= 4645756137312482954863057031577789954538271400. \end{align} $$

From here it is easy to check that the desired equality is true.