The binomial coefficient is connected to combinatorics (the field in math dealing with counting elements in various ways) and probability (the field in math dealing with chance of outcome), and represents the number of ways to choose discrete elements from a set, without considering the chosen elements order of appearance.

For example:

In a special three cup monte, there are two cups each hiding a little stone . a third cup is empty. All cups are facing down. The game master switches the cups around and asks the player to find the two cups hiding a stone.

Question: how many ways are there to hide two identical 2 small stones in 3 cups (where each cup cannot hold more than one stone)?

Let us first look at it in a graphic way (for intuition):

stone | stone | empty
stone | empty | stone
empty | stone | stone

So, there are only 3 ways to setup the configuration as we asked for.

Then, if we ask, what is the chance (probability) that the two stones are in the leftmost cups, the answer will be $\frac{1}{3}$.

Now, we will introduce the tool that generalizes the calculation of how to position 'k' elements in 'n' discrete containers, which is the binomial coefficient (also called in colloquial language 'k' choose 'n').

$$\binom{n}{k} = \frac{n!}{(n-k)!k!} \qquad k, n \in \N \quad 0 \leq k \leq n$$

Observe that for the cases $k < 0$ and $k > n$ the binomial coefficient value is 0 (intuitively, there are no ways to insert more elements than there are containers, such that each container has exactly one element, and no ways to insert a negative number of elements, which is trivial).

Now, that we are familiar with the binomial coefficient and its typical use, we will establish its validity and truth $\forall n \in \N$:

First we need to establish Pascal's formula as a lemma:

Proposition: $\forall n \in \N$, $k \in \N$, $0\leq k \leq n$,
$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$

Proof:

We will use a combinatorial argument to establish this formula.
Observe that given $n$ containers and $k$ elements, we can look at all the possible way to insert these $k$ elements into $n$ containers (such that each container doesn't include more than one element) in an alternative way, namely, by isolating and marking one of the containers.
Then, either we put something in the marked container, and then we need to insert the rest of the $k-1$ elements in the remaining $n-1$ containers, or we do not insert anything into this marked container, and then we just need to insert $k$ elements into $n-1$ containers. In any case, the binary choice of either placing or not placing in the marked container covers all the possibilities of distributing $k$ elements in $n$ containers in the method we've described.

In math notation, what was described above in an intuitive combinatorial way is written:

$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$

And so, we've established the validity of what is called Pascal's formula for the binomial coefficient.

Now, we can move on to establish the truth of the binomial formula:

Proposition: $\forall n \in \N$, $k \in \N$, $0\leq k \leq n$,
$ \quad \binom{n}{k} = \frac{n!}{(n-k)!k!}$

Proof:

Since the proposition applies to the naturals, we will use proof by induction over k.
1) Base case: $n=0$,

Then, by the definition, $0 \leq k \leq 0$, $$\binom{0}{0} = \frac{0!}{(0-0)!0!} = \frac{1}{1} = 1$$ The base case truth can be explained intuitively, since the number of ways to position 0 elements in 0 containers is definitely 1 (we can only do this in a single way, namely, not put anything in nothing).

2) Assume that $ \binom{n}{k} = \frac{n!}{(n-k)!k!}$ is true, $k \in \N$, $0\leq k \leq n$.

3) Inductive step:

For the last step, we utilize Pascal's formula, which we proved earlier.
$\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}=$ $\frac{n!}{(n-k)!k!}$ + $\frac{n!}{(n- (k - 1))!(k-1)!}$
$=\frac{n!}{(n-k)!k!} +$ $\frac{n!}{(n - k + 1)!(k-1)!} =$ $\frac{n! \cdot (n +1 -k) + n! \cdot k}{(n + 1 - k)!k!}$
$ = \frac{(n+1)! - n! \cdot k + n! \cdot k}{(n + 1 - k)!k!} = \frac{(n+1)!}{(n + 1 - k)!k!} \quad \Box$

Now, That We established the binomial coefficient formula and Pascal's formula we will state the binomial theorem and prove it:

$$\forall n \in \N, \quad (a+b)^n = \sum_{k=0}^{n} \binom{n}{k}a^{n-k}b^k$$

Proof of the binomial theorem:

1) Base case: $n=0$,

$(a+b)^0 = 1$
$\sum_{k=0}^0 \binom{0}{k}a^{0-k}b^k = a^{0-0}b^0 = 1 \cdot 1 = 1 $

2) Assume the proposition is true for n.

3) Inductive step:

$(a+b)^{n+1} = (a+b)(a+b)^n=(a+b) \cdot \sum_{k=0}^{n} \binom{n}{k}a^{n-k}b^k$
$= \sum_{k=0}^{n} \binom{n}{k} a^{n-k+1}b^k + \sum_{k=0}^{n} \binom{n}{k}a^{n-k}b^{k+1}$

Substitute the summation variable in the second term, $m = k + 1$:

$= \sum_{k=0}^{n} \binom{n}{k} a^{n-k+1}b^{k} + \sum_{m=1}^{n+1} \binom{n}{m -1}a^{n-m+1}b^{m}$

Now, in order for the summation bounds to be the same, we will isolate the first element from the first sum and last element of the second sum:

$= \binom {n}{0}a^{n+1}b^0 \ + \sum_{k=1}^{n} \binom{n}{k} a^{n-k+1}b^{k} + \sum_{m=1}^{n} \binom{n}{m -1}a^{n-m+1}b^{m} + \binom {n}{n}a^{0}b^{n+1}$

Now, we utilize Pascal's formula once again to fuse the inner terms into a single sum (the formal parameters $k$ and $m$ are only placeholders, so the fused sum will use a single formal parameter $k$):

$= \binom {n}{0}a^{n+1}b^0 \ + \sum_{k=1}^{n}[\binom{n}{k} + \binom {n}{k-1}]a^{n-k+1}b^k + \binom {n}{n}a^{0}b^{n+1}$

$= \binom {n}{0}a^{n+1}b^0 \ + \sum_{k=1}^{n}\binom{n+1}{k}a^{n+1-k}b^k + \binom {n}{n}a^{0}b^{n+1} = \sum_{k=0}^{n+1}\binom{n+1}{k}a^{n+1-k}b^k$

The last step Where we fused the isolated terms back into the summation, since:

$\binom{n}{0} = \binom {n+1}{0}$ and $\binom{n}{n} = \binom{n+1}{n+1} \quad \Box$

A variant useful form of the binomial is:

$(a-b)^n =[a+(-b)]^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}(-b)^k $

$ = \sum_{k=0}^{n} (-1)^k \cdot \binom{n}{k}a^{n-k}b^k $

Some typical algebraic identities in common use in algebra (especially high-school level) are special cases of the generalized binomial theorem:

$$(a+b)^2 = a^2 + 2ab + b^2$$
$$(a-b)^2 = a^2 -2ab + b^2$$
$$(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 $$
$$(a-b)^3 = a^3 - 3a^2b + 3ab^2 - b^3 $$

If we describe typical algebraic identities in commonly in use, there are 3 more that are not directly connected to the binomial, but we will write them down:

$$(a-b)(a+b) = a^2-b^2$$ $$a^3 + b^3 = (a^2 - ab + b^2)(a+b)$$ $$a^3 - b^3 = (a^2 + ab + b^2)(a-b) $$