The symbol
$$n\choose k$$
is a shorthand for "The number of ways to choose $k$ objects from a collection of $n$ objects."
That is: you have $n$ objects in a line. You select $k$ of them, and paint them red, and you paint the other $n-k$ blue. How many ways are there to do that so that the final result looks different?
A moment of reflection will convince you that you could have chosen $n-k$ of the objects to paint blue first, and painted the rest of the objects red. The answer shouldn't depend on something arbitrary like whether you pick up the blue or the red paint first. If you can grok this fact, then you will have proved to yourself that
$${n\choose k} = {n\choose n-k}$$
How does this relate to binomial expansions? Well, say that we want to expand
$$(r + b)^n$$
Then we'll get a bunch of terms, each of which is a product of some $r$s with some $b$s. There are $n$ brackets, so there will be $n$ multipliers in each of the terms, and each of them will be either $r$ or $b$, so every term looks like
$$a_kr^kb^{n-k}$$
where $a_k$ is a coefficient, and $k=0, 1, 2, \dots n$.
What is $a_k$? Notice that in every bracket, we have to choose either an $r$ or a $b$. We can imagine going through the brackets one by one and making these choices, or you can imagine looking at all the brackets at once, and choosing which of them to pick $r$ form and which to pick $b$ from. The coefficient $a_k$ is the number of different ways of picking $k$ $r$s and $(n-k)$ $bs$ from the $n$ brackets. That is:
$$a_k = {n\choose k}$$
which, using the fact from earlier, we can instantly use to prove that the coefficients in a binomial expansion are symmetric:
$$a_k = {n\choose k} = {n\choose n-k} = a_{n-k}$$
Maybe you can see how binomial expansions relate to Pascal's triangle now?
Hint: It is linked to another cool and exciting relationship between the binomial coefficients!
Let's give a combinatorial proof.
$\binom{n+1}{k+1}$ is the number of subsets of $[n] = \{0,1,2, \ldots, n\}$ having exactly $k+1$ elements. Looking at the smallest or largest element of such a subset makes sense.
Let's look at the second smallest element instead. It can be any number from $1$ (for subsets which have $0$ and $1$ as their two smallest elements) to $n-k+1$ (for subsets which have $n-k+1, \ldots, n-1, n$ as their $k$ largest elements).
So $$\binom{n+1}{k+1} = \sum_{i=1}^{n-k+1} \textrm{number of subsets having $i$ as 2nd smallest element}.$$
So how many $(k+1)$-element subsets of $[n]$ have $i$ as 2nd smallest elements?
Well, the recipe to make such a subset is clear:
- Chose any number in $0, 1, \ldots, i-1$ to serve as smallest element.
- Pick $i$ as second smallest element.
- Pick any $(k-1)$-element subset of $\{i+1, \ldots, n\}$ to serve as the $n-1$ elements larger than $i$.
In the first step, you have $i$ choices, the second step involves no choice and you have $\binom{n-i}{k-1}$ choices in the last step, because $\{i+1, \ldots, n\}$ has $n-i$ elements.
So the number of $(k+1)$-element subsets of $[n]$ having $i$ in second position is $i \binom{n-i}{k-1}$, which proves that
$$\binom{n+1}{k+1} = \sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}.$$
A slight generalisation of this proof shows that if $a+b=k$
$$ \binom{n+1}{k+1} = \sum_i \binom{i}{a}\binom{n-i}{b}:$$
you only have to look at the $(a+1)$-th largest element of the $(k+1)$-element subsets of $n+1$. We have just done the $a=1$ case.
Best Answer
Another way using generating functions. The identity can be obtained from taking the coefficient of $x^n$ in the expansions of both sides of the identity $$ \frac{1}{1-x}\times(1-x)^j=(1-x)^{j-1}. $$ The binomial theorem implies that $[x^n]((1-x)^{j-1})=(-1)^n\binom{j-1}{n}$ where $[x^n]$ means extract the coefficient of $x^n$ in the series.
Since $(1-x)^{-1}=\sum_{m=0}^\infty x^m$ and $(1-x)^j=\sum_{u=0}^j (-1)^u\binom{j}{u}$, the cauchy product implies that $[x^n](\frac{1}{1-x}\times(1-x)^j)=\sum_{k=0}^n(-1)^k\binom{j}{k}$ from which the result follows.