Binomial Coefficient Intuition

Question

Because every number in Pascal's Triangle is the sum of the two numbers above it, and because each number in the triangle is a combination of the form $\binom{n}{k}$, this implies the formula $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ (or something similar).

I can prove the formula algebraically, by expanding using factorials and simplifying. However, writing down the algebraic proof did not provide intuition about why the formula is true.

I wonder if there is an intuitive explanation for why, e.g., $\binom{7}{4}=\binom{6}{3}+\binom{6}{4}$, considering that these quantities can be thought of as the number of ways to choose objects out of a set.

Answer 1

You will want to think about ${n\choose k}$ as the number of $k$-element subsets of $\{1,2,...,n\}$. Then to show the identity, it suffices to show that both sides of the equation count the same number of things. ${n-1\choose k}$ counts the number of $k$-element subsets of $\{1,2,...,n\}$ which do not contain $n$, and ${n-1\choose k-1}$ counts the number of $k$-element subsets of $\{1,2,...,n\}$ which do contain $n$. Hence the result follows.

Answer 2

For each $k$-subset of $\{1,\dots,n\}$, consider whether element $n$ appears or not.

Answer 3

Yea, if you think about binary vectors and look at the most left spot for example, you have 2 choices, 1 or 0. now say you're looking to choose k 1's, meaning $\binom{n}{k}$ if you chose 0 then you need to choose k 1's out of n-1 spots meaning $\binom{n-1}{k}$ and if you chose 1 you need to choose k-1 1's out of n-1 spots meaning $\binom{n-1}{k-1}$ just like the identity you mentioned