math dump ¶

Contents

math dump

1 binomial coefficients ¶

a central binomial coefficient is a binomial coefficient of the form $\displaystyle \binom{2n}{n}$
Interpretation of binomial coefficients $N:=\displaystyle \binom{m}{n}$
- There are $N$ ways to choose $n$ elements from a set of $m$ elements.
- There are $N$ ways to choose $n$ objects from a collection (in which repetitions are allowed) of $m-n+1$ objects.
- There are $N$ strings containing $n$ ones and $m-n$ zeros.
- There are $N$ strings consisting of $n$ ones and $m-1$ zeros such that no two ones are adjacent.
- $\displaystyle (X+Y)^{n} = \sum_{k=0}^{n} \binom{n}{k} X^{n-k} Y^{k}$ for $n \in \mathbb{N}_{\ge 0}$ and $X,Y$ are indeterminates.

1.1 identities ¶

$\displaystyle \binom{m}{n} = \binom{m}{m-n}$ for $m,n\in\mathbb{N}_{\ge 0}$ such that $m \ge n$. However, for those $m$ and $n$, $\displaystyle \binom{-n}{m} \ne \binom{-n}{-n-m}$.
Pascal’s rule (Pascal’s triangle): $\displaystyle \binom{n}{k} + \binom{n}{k+1}=\binom{n+1}{k+1}$
$\displaystyle \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$
$\displaystyle \binom{n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}$
$\displaystyle \binom{n}{i} \binom{n-i}{j} = \binom{n}{j} \binom{n-j}{i}$
$\displaystyle \binom{n}{k} = \frac{n+1-k}{k} \binom{n}{k-1}$
$\displaystyle \int_{-\pi}^{\pi} \cos ((2m-n)x)\cos^{n}x\, dx = \frac{\pi}{2^{n-1}} \binom{n}{m}$
$\displaystyle \int_{-\pi}^{\pi} \sin((2m-n)x) \sin^{n}x \, dx = \begin{cases}(-1)^{m+(n+2)/2}\frac{\pi}{2^{n-1}}\binom{n}{m} & \text{ when } n\text{ is odd}\\ 0 & \text{ otherwise} \end{cases}$
$\displaystyle \int_{-\pi}^{\pi} \cos((2m-n)x) \sin^{n}x \, dx = \begin{cases}(-1)^{m+(n/2)}\frac{\pi}{2^{n-1}} \binom{n}{m} & \text{ when } n \text{ is even}\\ 0 & \text{ otherwise}\end{cases}$
$\displaystyle \binom{z}{k} = (-1)^{k} \binom{-z+k-1}{k} = \frac{(-1)^{k}}{(k+1)^{z+1}\cdot \Gamma(-z)} \prod_{j=k+1}^\infty \frac{(1+\frac{1}{j})^{-z-1}}{1- \frac{z+1}{j} }$ for $z \in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$
$\displaystyle \binom{1/2}{k} = \binom{2k}{k} \frac{(-1)^{k+1}}{2^{2k}(2k-1)}$ for $k \in \mathbb{N}_{\ge 0}$
$\displaystyle \binom{w}{z} = \frac{\sin z\pi}{\sin w\pi} \binom{-z-1}{-w-1} = \frac{\sin (w-z)\pi}{\sin w\pi} \binom{z-w-1}{z}$ for $w,z\in\mathbb{C}$
$\displaystyle \binom{w}{z} \binom{z}{w} = \frac{\sin (w-z)\pi}{(w-z)\pi}$ for $w,z\in\mathbb{C}$
$\displaystyle \binom{w}{z} = \frac{\Gamma(w+1)}{\Gamma(z+1)\Gamma(w-z+1)} = \frac{1}{(w+1)B(w-z+1,z+1)}$ where $B(\_,\_)$ is the Beta function for $w,z\in\mathbb{C}$

1.2 Stirling number ¶

$\displaystyle \binom{t}{k} = \sum_{i=0}^{k} s(k,i)\frac{t^{i}}{k!}$ where $s(k,i)$ is the Stirling number of the first kind
$\displaystyle \binom{z}{n} = \frac{1}{n!} \sum_{k=0}^{n} z^{k} s(n,k) = \sum_{k=0}^{n} (z-z_{0})^{k} \sum_{l=k}^{n} \binom{z_{0}}{l-k} \frac{s(n+k-j,k)}{(n+k-j)!} = \sum_{k=0}^{n} (z-z_{0})^{k} \sum_{l=k}^{n} z_{0}^{l-k} \binom{l}{k} \frac{s(n,l)}{n!}$ for $z,z_{0}\in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$

1.3 derivatives ¶

$\displaystyle \frac{d}{dt} \binom{t}{k} = \binom{t}{k} \sum_{i=0}^{k-1} \frac{1}{t-i}$

1.4 relationship with polynomials ¶

$\displaystyle (X+Y)^{n} = \sum_{k=0}^{n} \binom{n}{k} X^{n-k} Y^{k}$ for $n \in \mathbb{N}_{\ge 0}$ and $X,Y$ are indeterminates.
for a field $K$ of characteristic $0$, $P(t) \in K[t]$ is uniquely expressed as $\displaystyle P(t) = \sum_{k=0}^{\deg P} a_{k} \binom{t}{k}$ where $\displaystyle a_{k} = (-1)^{k-i} \binom{k}{i} P(i)$ , the /k/th difference of the sequence $P(0),P(1),\ldots,P(k)$
$\displaystyle \sum_{j=0}^{n} (-1)^{j} \binom{n}{j} P(j) = 0$ where $P(j)$ is a polynomial of degree $< n$
$\displaystyle \sum_{j=0}^{n} (-1)^{j} \binom{n}{j} P(m+(n-j)d) = d^{n}\cdot n!\cdot a_{n}$ where $P(x)$ is a polynomial of degree $\le n$, $a_{n}$ is its coefficient of degree $n$ and $m,d\in \mathbb{C}$

1.5 finite sums ¶

$\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$
$\displaystyle \sum_{k=0}^{n} k \binom{n}{k} = n 2^{n-1}$
$\displaystyle \sum_{k=0}^{n} k^2 \binom{n}{k} = (n+n^{2})2^{n-2}$
Chu-Vandermonde identity: $\displaystyle \sum_{j=0}^{k} \binom{m}{j} \binom{n-m}{k-j} = \binom{n}{k}$
$\displaystyle \sum_{j=0}^{m} \binom{m}{j}^{2} = \binom{2m}{m}$
$\displaystyle \sum_{m=k}^{n} \binom{m}{k} = \binom{n+1}{k+1}$
$\displaystyle \sum_{r=0}^{m} \binom{n+r}{r} = \binom{n+m+1}{m}$
$\displaystyle \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k} = F(n+1)$ where $F(n)$ is the $n$ th Fibonacci number
$\displaystyle \binom{n}{t} + \binom{n}{t+s} + \binom{n}{t+2s} + \cdots = \frac{1}{s} \sum_{j=0}^{s-1} \left(2 \cos \frac{\pi j}{s} \right)^{n} \cos \frac{\pi (n-2t) j}{s}$ Proof. This follows from the multisection of a binomial expansion

\[(1+x)^{n} = \binom{n}{0}x^{0} + \binom{n}{1} x + \binom{n}{2} x^{2} +\cdots\]
$\displaystyle \sum_{j=0}^{k} (-1)^{j} \binom{n}{j} = (-1)^{k} \binom{n-1}{k}$
$\displaystyle \sum_{j=0}^{n} (-1)^{j} \binom{n}{j} P(j) = 0$ where $P(j)$ is a polynomial of degree $< n$
$\displaystyle \sum_{j=0}^{n} (-1)^{j} \binom{n}{j} P(m+(n-j)d) = d^{n}\cdot n!\cdot a_{n}$ where $P(x)$ is a polynomial of degree $\le n$, $a_{n}$ is its coefficient of degree $n$ and $m,d\in \mathbb{C}$
$\displaystyle \sum_{k-q}^{n} \binom{n}{k} \binom{k}{q} = 2^{n-q} \binom{n}{q}$
$\displaystyle \binom{z}{m} \binom{z}{n} = \sum_{k=0}^{m} \binom{m+n-k}{k,m-k,n-k} \binom{z}{m+n-k}$ for $z\in\mathbb{C}$ and $m,n\in\mathbb{N}_{\ge 0}$
Dixon’s identity: $\displaystyle \sum_{k=-a}^{a} (-1)^{k} \binom{a+b}{a+k} \binom{b+c}{b+k} \binom{c+a}{c+k} = \frac{(a+b+c)!}{a! b! c!}$ where $a,b,c \in \mathbb{N}_{\ge 0}$
$\displaystyle \binom{z}{n}^{-1} = \sum_{k=0}^{n-1} (-1)^{n-1-k} \binom{n}{k} \frac{n-k}{z-k}$ for $z\in\mathbb{C}$ and $n\in\mathbb{N}_{\ge 0}$
$\displaystyle \binom{z+n}{n}^{-1} = \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{k}{z+k}$ for $z\in\mathbb{C}$ and $n\in\mathbb{N}_{\ge 0}$

1.6 series, generating functions ¶

$\displaystyle (1+z)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} z^{k}$ for any $\alpha,z\in \mathbb{C}$ with the radius for convergence $1$.
$\displaystyle \frac{k-1}{k} \sum_{j=0}^{\infty} \frac{1}{\binom{j+x}{k} }= \frac{1}{\binom{x-1}{k-1} }$ converges for $k \ge 2$
$\displaystyle \sum_{k=0}^{\infty} \binom{n}{k} x^{k} = (1+x)^{n}$
$\displaystyle \sum_{n=k}^{\infty} \binom{n}{k} y^{n} = \frac{y^{k}}{(1-y)^{k+1}}$
$\displaystyle \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n} = \frac{1}{1-y-xy}$
$\displaystyle \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \binom{n+k}{k} x^{k} y^{n} = \frac{1}{1-x-y}$
$\displaystyle \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \binom{n+k}{k} \frac{x^{k} y^{n}}{(n+k)!} = e^{x+y}$
Newton’s binomial series: $\displaystyle (1+z)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} z^{k}$ for $z,\alpha \in \mathbb{C}$ with the radius of convergence is $1$.
$\displaystyle (1-z)^{-(\alpha+1)} = \sum_{k=0}^{\infty} \binom{k+\alpha}{k} z^{k}$ for $z,\alpha \in \mathbb{C}$ with the radius of convergence is $1$.

1.7 divisibility ¶

Kummer: $\displaystyle \forall m,n \in \mathbb{N}_{\ge 0}, \forall$ prime $p$, $\displaystyle \max\left\{ a \in \mathbb{N}_{\ge 0} \mid p^{a}\Bigg| \binom{m+n}{m}\right\} =$ the number of carries when $m$ and $n$ are added in base $p$ $= \# \{j \in \mathbb{N}_{\ge 0} \mid {}$ the fractional part of $m/p^{j}$ is greater than the fractional part of $(m+n)/p^j\}$
$\displaystyle \frac{n}{\mathrm{GCD}(n,k)}\Big| \binom{n}{k}$
$\displaystyle p\Big| \binom{p^r}{s}$ for $\displaystyle \forall r,s \in \mathbb{Z}$ such that $s < p^{r}$ where $p$ is a prime number but $\displaystyle p^{k}\not\Big| \binom{p^r}{s}$ in general for $k \ge 2$, for eg, $\displaystyle 3^{2}\not\Big| \binom{9}{6}$
Singmaster: any integer divides almost all binomial coefficients. Note that the number of binomial coefficient $\binom{n}{k}$ with $n<N$ is $N(N+1)/2$. Let $f(d,N)$ be the number of binomial coefficients $\binom{n}{k}$ with $n< N$ such that $d | \binom{n}{k}$. Then, for any $d$, $\displaystyle \lim_{N\rightarrow \infty} \frac{f(d,N)}{N(N+1)/2} = 1$
$\displaystyle \frac{\mathrm{LCM}(n,n+1,\ldots,n+k)}{n\cdot \mathrm{LCM} \left(\binom{k}{0}, \binom{k}{1}, \ldots, \binom{k}{k} \right)} \ \Big| \ \binom{n+k}{k} \ \Big| \ \frac{\mathrm{LCM}(n,n+1,\ldots,n+k)}{n}$
$n \ge 2$ is prime $\displaystyle \Leftrightarrow \forall 1 \le k < n,\, n\Big| \binom{n}{k}$

1.8 inequalities ¶

$\displaystyle \frac{n^{k}}{k^{k}} \le \binom{n}{k} \le \frac{n^{k}}{k!} < \Big(\frac{n\cdot e}{k} \Big)^k$ for $1 \le k \le n$
$\displaystyle \binom{mn}{n} \ge \frac{m^{m(n-1)+1}}{\sqrt{n}\cdot (m-1)^{(m-1)(n-1)}}$ for $m\ge 2$ and $n\ge 1$
$\displaystyle \sum_{i=0}^{k} \binom{n}{i} \le \sum_{i=0}^{k} n^{i}\cdot 1^{k-i} \le (1+n)^{k}$
$\displaystyle \frac{2^{n\cdot H(\varepsilon)}}{\sqrt{8 n \varepsilon (1-\varepsilon)}} \le \sum_{i=0}^{k} \binom{n}{i} \le 2^{n\cdot H(\varepsilon)}$ for any integers $n\ge k\ge 1$ with $\varepsilon {}\dot{=}{} k/2 \le 1/2$ and $H$ is the binary entropy function

1.9 asymptotes ¶

$\displaystyle \binom{n}{k} \sim \sqrt{\frac{n}{2 \pi k (n-k)} } \cdot \frac{ n^{n}}{k^{k}(n-k)^{n-k}}$ for $n,k \gg 0$
$\displaystyle \binom{2n}{n} \sim \frac{2^{2n}}{\sqrt{\pi n}}$ for $n \gg 0$
$\displaystyle \binom{n}{k} \sim 2^{nH(k/n)}$ where $H$ is the binary entropy function $H(p) := -p \log_{2}(p)-(1-p)\log_{2} (1-p)$
$\displaystyle \binom{n}{k} \approx \frac{(n-k/2)^{k}}{k^{k} e^{-k} \sqrt{2\pi k}} = \frac{(n/k-1/2)^{k} e^{k}}{\sqrt{2 \pi k}}$ for $n\gg 0$ and $k \ll n$
$\displaystyle \binom{n}{k} \approx \exp\Big( k \log (n/k-1/2)+k - 1/2 \log (2\pi k)\Big)$ for $n\gg 0$ and $k \ll n$
$\displaystyle \binom{n}{k} \approx \exp \Big( (n+1/2)\log \frac{n+1/2}{n-k+1/2} + k \log \frac{n-k+1/2}{k} - 1/2 \log (2\pi k) \Big)$ for $n\gg 0$ and $k \ll n$
$\displaystyle \binom{n}{k} \sim \binom{n}{n/2} e^{-d^{2}/(2n)} \sim \frac{2^{n}}{\sqrt{2^{-1} n \pi}} e^{-d^{2}/(2n)}$ where $d=n-2k$ for $n \gg 0$ and $|n/2-k| = o(n^{2/3})$ (so that $n \propto k$)
$\displaystyle \binom{z}{k} \approx \frac{(-1)^{k}}{k^{z+1}\cdot \Gamma(-z)}$ for $z \in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$ such that $k \gg 0$
$\displaystyle \binom{z}{k} \approx \frac{(-1)^{k}}{k^{z+1}\cdot \Gamma(-z)}$ for $z \in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$ such that $k \gg 0$
$\displaystyle \binom{z+k}{k} = \frac{k^{z}}{\Gamma(z+1)} \Big(1 + \frac{z(z+1)}{2k} + O(k^{-2}) \Big)$ for $z \in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$ such that $k \gg 0$
$\displaystyle \binom{z+k}{k} \approx \frac{e^{z(H_{k}-\gamma)}}{\Gamma(z+1)}$ for $z \in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$ such that $k \gg 0$ where $H_{k}$ is the $k$ th harmonic number and $\gamma$ is the Euler-Mascheroni constant.
$\displaystyle \lim_{k \rightarrow \infty} \binom{z+k}{j} \Bigg{/} \binom{k}{j} = \left(1- \frac{j}{k} \right)^{-z}$ for $z,j \in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$ where $j/k$ converges in $\mathbb{C}$
$\displaystyle \lim_{k\rightarrow \infty} \binom{j}{j-k}\Bigg{/} \binom{j-z}{j-k} = \left(\frac{j}{k}\right)^{z}$ for $z,j \in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$ where $j/k$ converges in $\mathbb{C}$

1.10 the gamma function ¶

$\displaystyle \binom{z}{k} = (-1)^{k} \binom{-z+k-1}{k} = \frac{(-1)^{k}}{(k+1)^{z+1}\cdot \Gamma(-z)} \prod_{j=k+1}^\infty \frac{(1+\frac{1}{j})^{-z-1}}{1- \frac{z+1}{j} }$ for $z \in \mathbb{C}$ and $k \in \mathbb{N}_{\ge 0}$
$\displaystyle \binom{w}{z} = \frac{\Gamma(w+1)}{\Gamma(z+1)\Gamma(w-z+1)} = \frac{1}{(w+1)B(w-z+1,z+1)}$ where $B(\_,\_)$ is the Beta function for $w,z\in\mathbb{C}$

1.11 the beta function ¶

$\displaystyle \binom{w}{z} = \frac{\Gamma(w+1)}{\Gamma(z+1)\Gamma(w-z+1)} = \frac{1}{(w+1)B(w-z+1,z+1)}$ where $B(\_,\_)$ is the Beta function for $w,z\in\mathbb{C}$

2 Stirling numbers ¶

Stirling numbers of the first kind: $\displaystyle \frac{x!}{n!} = \sum_{k=0}^{n} s(n,k)x^k$

table for $s(n,k)$

nk	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1
9	0	40320	109584	118124	67284	22449	4536	546	36	1

3 Fibonacci number ¶

$\displaystyle \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k} = F(n+1)$ where $F(n)$ is the $n$ th Fibonacci number

4 trigonometric functions ¶

5 series multisection ¶

6 Beta function ¶

For $w,z\in \mathbb{C}$ both with strictly positive real parts, the beta function is defined as an integral over the unit interval on $\mathbb{R}$ as

\[B(w,z) := \int_{0}^{1} t^{w-1}(1-t)^{z-1} \, dt\]
For $w,z\in \mathbb{C}$ both with strictly positive real parts and $x\in \mathbb{R}$, the incomplete beta function is defined as an integral over an interval on $\mathbb{R}$ as

\[B(x;w,z) := \int_{0}^{x} t^{w-1}(1-t)^{z-1} \, dt\]
For $w,z\in \mathbb{C}$ both with strictly positive real parts and $x\in \mathbb{R}$, the regularized (incomplete) beta function is defined as the ratio

\[I_{x}(w,z) := \frac{B(x;w,z)}{B(w,z)}\]
The $boldsymbol{F}$-distribution $F(k;n,p)$ is a discrete probability distribution describing the probability of having $\lfloor k\rfloor$ times of success, regardless of the order, of probability $p$ out of $n$ trials:

\[F(k;n,p) := \sum_{i=0}^{k} \binom{n}{i} p^{i}(1-p)^{n-i} = I_{1-p}(n-k,k+1)\]

7 Euler integral of the first kind ¶

This is an another name for the beta function.