Combinations, Binomial Coefficients, and Pascal's Triangle

Here, you might have already encountered Pascal's triangle. This explanation mentions how if we consider an 'addition triangle', then the $k$-th term in the $n$-th row is equal to $\binom nk$. It mentions a few patterns - how the sum of terms in the $n$-th row is $2^n$, or the Hockey Stick Identity, and finally, the Binomial Expansion.

(Here, we will use the notation $\binom nk$ for $nCk$ - I believe it is more common in mathematical literature.)

The goal of this explanation is to prove these observations, and show some basic techniques for operating with binomial coefficients.

There are two tools we will thoroughly use:

1. the identity $\binom{n+1}{k+1}=\binom nk+\binom n{k+1}$,

2. the Binomial Theorem $$(a+b)^n=\binom nn a^n+\dots+\binom nk a^kb^{n-k}+\dots+\binom n0 b^n.$$

The Binomial Theorem is proven in the link, and the second identity follows from expanding the formula $\binom nk=\frac{n!}{k!(n-k)!}$.

First of all, let's establish that the Pascal Triangle indeed is the same as the binomial coefficients arranged into a triangle. To see this, it is enough to show that both have that addition property that each term is the sum of the two terms above it, because due to $\binom n0=\binom nn=1$, the numbers on the sides of both triangles are all $1$.

The Hockey Stick Identity just follows from using 1) again and again. Written with binomial coefficients, it looks like this:

\begin{align} \binom nk&=\binom{n-1}{k-1}+\binom{n-1}k \ &= \binom{n-1}{k-1}+\binom{n-2}{k-1}+\binom{n-2}k \ &= \dots \ &= \binom{n-1}{k-1}+\binom{n-2}{k-1}+\dots+\binom{k}{k-1}+\binom{k}{k} \ &= \binom{n-1}{k-1}+\binom{n-2}{k-1}+\dots+\binom{k}{k-1}+\binom{k-1}{k-1} \end{align}

Another observation was that the sum of the numbers in the $n$-th row of the Pascal Triangle is $$\binom n0+\binom n1+\dots+\binom nn=2^n.$$

I would like to mention one more important property of the Pascal Triangle. This is almost too obvious to mention: the numbers in each row increase until the middle, and then they start decreasing.

If we expanded them, we'd get

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

Hence, this fraction is $<1$ if $k+1<n-k$, i.e. $k<\frac{2n-1}2$, it is $=1$ if $k=\frac{2n-1}2$ and it is $>1$ if $k>\frac{2n-1}2$. Therefore, if $n$ is even, i.e. $n=2m$, then

$$\binom{2m}0<\binom{2m}1<\dots<\binom{2m}{m-1}<\binom{2m}m>\binom{2m}{m+1}>\dots>\binom{2m}{2m},$$

and if $n=2m-1$, then

$$\binom{2m-1}0<\dots<\binom{2m-1}{m-1}=\binom{2m-1}{m}>\dots>\binom{2m-1}{2m-1}.$$

What can we deduce from here? Since $\binom{2m}{m}$ is the largest number in the $2m$-th row of the Pascal Triangle, it is larger than the average of the numbers in the $2m$-th row, which is $\frac{2^{2m}}{2m+1}$. Similarly, $\binom{2m-1}{m}>\frac{2^{2m-1}}{2m}$. However, we still have $\binom{2m}{m}<2^{2m}$ and $\binom{2m-1}{m}+\binom{2m-1}{m-1}<2^{2m-1}$, so $\binom{2m-1}{m}<2^{2m-2}$.

A similarly important result is that

$$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}.$$

Note that

$$\binom{2n}{n}=\frac{(2n)!}{n!\cdot n!}=\frac{2n}{n}\cdot \frac{2n-1}{n}\cdot \frac{2n-2}{n-1}\cdot \frac{2n-3}{n-1}\cdot \frac{2n-4}{n-2}\cdot \ldots\cdot \frac{2}{1}\cdot \frac{1}{1}$$ $$=2^{2n}\cdot \underbrace{\frac{2n-1}{2n}\cdot \frac{2n-3}{2n-2}\cdot \ldots\cdot \frac34\cdot \frac12}_{=A}.$$

Now compare $A$ with

$$B=\frac{2n}{2n+1}\cdot \frac{2n-2}{2n-1}\cdot \ldots\cdot \frac45\cdot \frac{2}{3}$$

and

$$C=\left(\frac{2n-2}{2n-1}\cdot \frac{2n-4}{2n-3}\cdot \ldots\cdot \frac23\right)\cdot \frac12.$$

Using this, can you deduce estimates for $\displaystyle\binom{2n}{n}$?

Prove that if $p$ is a prime number, then $p$ divides

$$(x+1)^p-(x^p+1).$$

Deduce Fermat's Little Theorem.

a) Prove that $k$ divides $\displaystyle\binom{nk}{n}$.

b) Prove that $n$ divides $\displaystyle\binom{n}{k}\cdot \text{gcd}(n,k)$.

(Source: KöMaL, B.4397.)

Prove the following estimate:

$$2\binom{2m-1}{m-1}=\binom{2m}{m}>\frac{4^m}{2m}.$$