Binomial coefficients
Proof:
$$ \frac{ \binom{n}{k - 1} \binom{n}{k + 1}}{\binom{n}{k}^2} > 1 $$According to the definition of the binomial coefficient, simplifying the expression proves the above identity
Proof:
Note by Binomial Theorem
$$ (1+x)^n=\sum_{k=0}^{n} \binom{n}{k} x^k $$Let $x = 1$
Proof:
Similarly to the previous proposition，Let $x = -1$
Proof:
$$ \begin{aligned} \binom{n-1}{k-1}+\binom{n-1}{k}&= \frac{(n-1)_{k-1}}{(k-1)!}+ \frac{(n-1)_k}{k!}\\&= \frac{(n-1)_{k-1}}{k!}\cdot k+ \frac{(n-1)_{k-1}}{k!}\cdot(n-k)\\&= \frac{(n-1)_{k-1}}{k!}\cdot n= \binom{n}{k}. \end{aligned} $$sometimes we just need to evaluate approximate value,so we use Stirling’s formula
$$ n! \approx \sqrt{2\pi n} \binom{n}{e}^n $$more precisely
$$ \lim_{n\to\infty} \frac{n!e^n}{n^n\sqrt{n}}= \sqrt{2\pi}. $$so we can approximate the bound
$$ \left(\frac{n}{k}\right)^k\le \binom{n}{k}\le \left(\frac{en}{k}\right)^k. $$we can easily proof the upper bound by the definition of binomial coefficient and Stirling’s formula
For the lower bound, we use the definition of the binomial coefficient together with the elementary estimate $k! \le k^k$. Indeed,
$$ \binom{n}{k}= \frac{n(n-1)\cdots(n-k+1)}{k!}\ge \frac{(n-k+1)^k}{k^k}= \left(\frac{n-k+1}{k}\right)^k. $$In particular, when $k \ll n$, this is asymptotically comparable to
$$ \left(\frac{n}{k}\right)^k. $$Further,a more precise approximation can be given by
$$ \binom{n}{k}\approx \sqrt{\frac{n}{2\pi k(n-k)}} \frac{n^n}{k^k(n-k)^{n-k}}\ge \frac{1}{\sqrt{2\pi k}} \frac{n^n}{k^k(n-k)^{n-k}}, $$$$ \binom{n}{k}= \frac{(n)_k}{k!}\le \frac{1}{\sqrt{2\pi k}} \frac{n(n-k/2)^{k-1}}{(k/e)^k}\le \frac{1}{\sqrt{2\pi k}} \frac{n^k}{(k/e)^k}. $$Substituting Stirling’s formula into the definition of the binomial coefficient yields the first estimate
For the second estimate, we combine Stirling’s formula with the elementary bound
$$ (n)_k= n(n-1)\cdots(n-k+1)\le n\left(n-\frac{k}{2}\right)^{k-1}. $$For odd k,we have
$$ (n)_k\le n\left(n-\frac{k - 1}{2}\right)^{k}. $$Proof:
Equivalent to proving the following identity
$$ \binom{n}{m}\equiv \binom{\,n \bmod p\,}{\,m \bmod p\,} \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor}\pmod p $$for convenience,we assume that $n \ge m$ and $n,m \in \mathbb{N}$,Let $n = sp + r,m=tp+w$ where $0≤r,w≤p−1$
Note that
$$ \begin{aligned} n!&= (sp+r)\cdots(sp+1) \prod_{i=0}^{s-1} \bigl((ip+1)\cdots(ip+p)\bigr) \\&= (r!+\alpha_0 p) \prod_{i=1}^{s} \bigl(ip((p-1)!+\alpha_i p)\bigr) \\&= s!p^s(r!+\alpha_0 p) \prod_{i=1}^{s} \bigl((p-1)!+\alpha_i p\bigr) \\&= s!p^s \bigl((-1)^s r! + Ap\bigr) \end{aligned} $$For $\alpha_0 \dots \alpha_s,A \in \mathbb{N}$，Similarly,For $m = tp+w$,we have
$$ m!= t!p^t \bigl((-1)^t w! + Bp\bigr) $$we apply Wilson theorem here:
$$ (p−1)!≡−1(modp) $$for some $B \in $,because of $n−m=(s−t)p+(r−w),$we have
$$ (n-m)!= \begin{cases} (s-t)!p^{s-t} \bigl((-1)^{s-t}(r-w)!+Cp\bigr),& r \ge w, \\[4pt] (s-t-1)!p^{s-t-1} \bigl((-1)^{s-t-1}(r+p-w)!+Cp\bigr),& r < w. \end{cases} $$for some $C \in \mathbb{N}$,now,if $r \ge w$,it follows that
$$ \begin{aligned} \binom{n}{m}&\equiv \frac{n!}{m!(n-m)!} \\[6pt]&\equiv \frac{s!p^s\bigl((-1)^s r!+Ap\bigr) }{t!p^t\bigl((-1)^t w!+Bp\bigr)\cdot(s-t)!p^{s-t}\bigl((-1)^{s-t}(r-w)!+Cp\bigr) } \\[6pt]&\equiv \frac{s!}{t!(s-t)!}\cdot \frac{(-1)^s r!+Ap}{(-1)^s w!(r-w)!+Dp} \\[6pt]&\equiv \binom{s}{t}\binom{r}{w}\pmod p \end{aligned} $$if $r < w$,we get$\binom{n}{m}\equiv0 \pmod{p}$ since the numerator has term $p^s$ but the denominator only has term $p^{s-1}$.But in the case,we also have $\binom{r}{w} = 0$,so we get
$$ \binom{n}{m} \equiv \binom{s}{t} \binom{r}{w} \pmod{p} $$A generalized version of binomial coefficients is the multinomial coefficients in the multinomial theorem,suppose $n=r_1+ \dots + r_m$ where $r_1, \dots,r_m$ are nonnegative integers. Define the multinomial coefficient as
$$ \begin{aligned}\left( \begin{array}{c}n \\r_1,\ldots,r_m \end{array}\right)&\triangleq\binom{n}{r_1}\binom{n-r_1}{r_2}\cdots\binom{n-r_1-\cdots-r_{m-1}}{r_m} \\[6pt]&=\frac{n!}{r_1!r_2!\cdots r_m!} \end{aligned} $$Then the multinomial theorem states that
$$ (x_1+\cdots+x_m)^n= \sum_{r_1+\cdots+r_m=n}\left( \begin{array}{c}n \\r_1,\ldots,r_m \end{array} \right)x_1^{r_1}\cdots x_m^{r_m} $$