Show ${156 \choose 87} + {156 \choose 86} = {157 \choose 87}$ How can we show the following equality?
$${156 \choose 87} + {156 \choose 86} = {157 \choose 87}$$
 A: 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?
A: 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.
A: 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.
A: 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.
