nyuuzyou/wikis huggingface dataset:
Binet's Formula for Logarithm of Gamma Function/Formulation 1/Corollary

== Corollary to Binet's Formula for Logarithm of Gamma Function: Formulation 1 == 
Let $z$ be a complex number with a positive real part.
Then: 
:$\ds \lim_{z \mathop \to \infty} \size {\Ln \map \Gamma z - \paren {z - \frac 1 2} \Ln z + z - \frac 1 2 \ln 2 \pi } \to 0$
where: 
:$\Gamma$ is the Gamma function
:$\Ln$ is the principal branch of the complex logarithm. 
== Proof ==
Category:Binet's Formula for Logarithm of Gamma Function
Binet's Formula for Logarithm of Gamma Function/Formulation 2

== Theorem == 
Let $z$ be a complex number with a strictly positive real part.
Then: 
:$\ds \Ln \map \Gamma z = \paren {z - \frac 1 2} \Ln z - z + \frac 1 2 \ln 2 \pi + 2 \int_0^\infty \frac {\map \arctan {t / z} } {e^{2 \pi t} - 1} \rd t$
where: 
:$\Gamma$ is the Gamma function
:$\Ln$ is the principal branch of the complex logarithm. 
== Proof == 
We have:
Recall the Abel-Plana Formula:
:$\ds \sum_{n \mathop = 0}^\infty \map f n = \int_0^\infty \map f x \rd x + \dfrac 1 2 \map f 0 + i \int_0^\infty \dfrac {\map f {i t} - \map f {-i t} } {e^{2 \pi t} - 1} \rd t$
Since: 
:$\ds \map f z = \dfrac 1 {\paren {z + k}^2 }$
Then:
$\map {f^{\paren k} } z = \paren {-1}^k \paren {k + 1}! \paren {z + k}^{-2 - k}$
where:
:$f^{\paren k}$ denotes the $k$th derivative of $f$
Therefore,
:$\ds \map f z = \dfrac 1 {\paren {z + k}^2 }$ is analytic for real part $\map \Re z > 0$.
Furthermore, since the Hurwitz Zeta Function is defined for $\set {\map \Re s > 1, a \ne 0, -1, -2, \cdots}$,
Therefore:
:$\ds \sum_{k \mathop = 0}^\infty \dfrac 1 {\paren {z + k}^2 }$ converges for real part $\map \Re z > 0$.
We also have that:
:$\ds \lim_{y \mathop \to \infty} \size {\dfrac 1 {\paren {\paren {x \pm i y} + k}^2 } } e^{-2 \pi y} = 0$ uniformly in $x$ on every finite interval and
:$\ds \int_0^{\infty} \size {\dfrac 1 {\paren {\paren {x \pm i y} + k}^2 } } e^{-2 \pi y} \rd y$ exists for every $x > 0$ and tends to $0$ as $x \to \infty$.
Therefore, we are justified in invoking the Abel-Plana Formula:
From the Fundamental Theorem of Calculus, we have $\ds \int \int \map {\dfrac {\d^2} {\d z^2} } {\Ln \map \Gamma z } \rd z \rd z = \Ln \map \Gamma z $
Therefore:
From Arctangent of Zero is Zero we have:
:$\ds \lim_{z \mathop \to \infty} \int_0^\infty \frac {\map \arctan {t / z} } {e^{2 \pi t} - 1} \rd t \to 0$
Therefore, we have:
:$\ds \lim_{z \mathop \to \infty} \size {\map \Ln {\map \Gamma {z } } - \paren {z - \frac 1 2} \Ln z - \paren {C_1 - 1} z - C_2} \to 0$
From , we have:
:$\ds \lim_{z \mathop \to \infty} \size {\Ln \map \Gamma z - \paren {z - \frac 1 2} \Ln z + z - \frac 1 2 \ln 2 \pi } \to 0$
Therefore: $C_1 = 0$ and $C_2 = \dfrac 1 2 \ln 2 \pi$
Therefore:
:$\ds \Ln \map \Gamma z = \paren {z - \frac 1 2} \Ln z - z + \frac 1 2 \ln 2 \pi + 2 \int_0^\infty \frac {\map \arctan {t / z} } {e^{2 \pi t} - 1} \rd t$
== Sources == 
* : $12.32$: Binet's second expression for $\log \Gamma \paren z$ in terms of an infinite integral
Category:Binet's Formula for Logarithm of Gamma Function
Binet-Cauchy Identity

== Theorem ==
:$\ds \paren {\sum_{i \mathop = 1}^n a_i c_i} \paren {\sum_{j \mathop = 1}^n b_j d_j} = \paren {\sum_{i \mathop = 1}^n a_i d_i} \paren {\sum_{j \mathop = 1}^n b_j c_j} + \sum_{1 \mathop \le i \mathop < j \mathop \le n} \paren {a_i b_j - a_j b_i} \paren {c_i d_j - c_j d_i}$
where all of the $a, b, c, d$ are elements of a commutative ring.
Thus the identity holds for $\Z, \Q, \R, \C$.
== Proof 1 ==
== Proof 2 ==
== Also known as ==
The Binet-Cauchy Identity is also known as Binet's formula.
== Historical Note ==
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $30$
Category:Summations
Category:Binet-Cauchy Identity
Binet-Cauchy Identity/Proof 2

== Theorem ==
== Proof ==
This is a special case of the Cauchy-Binet Formula:
:$\ds \map \det {\mathbf A \mathbf B} = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \cdots \mathop < j_m \le n} \map \det {\mathbf A_{j_1 j_2 \ldots j_m} } \map \det {\mathbf B_{j_1 j_2 \ldots j_m} }$
where:
:$\mathbf A$ is an $m \times n$ matrix
:$\mathbf B$ is an $n \times m$ matrix.
:For $1 \le j_1, j_2, \ldots, j_m \le n$:
::$\mathbf A_{j_1 j_2 \ldots j_m}$ denotes the $m \times m$ matrix consisting of columns $j_1, j_2, \ldots, j_m$ of $\mathbf A$.
::$\mathbf B_{j_1 j_2 \ldots j_m}$ denotes the $m \times m$ matrix consisting of rows $j_1, j_2, \ldots, j_m$ of $\mathbf B$.
In this case $m = 2$, giving:
:$\ds \map \det {\mathbf A \mathbf B} = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop \le n} \map \det {\mathbf A_{j_1 j_2} } \, \map \det {\mathbf B_{j_1 j_2} }$
== Historical Note ==
== Sources ==
* : $\S 1.2.3$: Sums and Products: Exercise $46 \ \text{(v)}$
Category:Binet-Cauchy Identity
Binet Form/First Form

== Theorem ==
Let $m \in \R$.
Define:
The recursive sequence:
:$U_n = m U_{n - 1} + U_{n - 2}$
where:
has the closed-form solution:
:$U_n = \dfrac {\alpha^n - \beta^n} \Delta$
== Proof ==
Proof by induction:
Let $\map P n$ be the proposition:
:$U_n = \dfrac {\alpha^n - \beta^n} \Delta$
=== Basis for the Induction ===
We have:
Therefore $\map P 0$ and $\map P 1$ are true.
This is the basis for the induction.
=== Induction Hypothesis ===
This is our induction hypothesis:
:For some $k \in \N$, both $\map P k$ and $\map P {k + 1}$ are true.
That is:
:$U_k = \dfrac {\alpha^k - \beta^k} \Delta$
:$U_{k + 1} = \dfrac {\alpha^{k + 1} - \beta^{k + 1}} \Delta$
Now we need to show true for $n = k + 2$:
:$\map P {k + 2}$ is true.
That is:
:$U_{k + 2} = \dfrac {\alpha^{k + 2} - \beta^{k + 2}} \Delta$
=== Induction Step ===
This is our induction step:
First we notice that:
Similarly:
Thus:
This show that $\map P {k + 2}$ is true.
By principle of mathematical induction, $\map P n$ is true for all $n \in \N$.
Category:Binet Form
Binet Form/Second Form

== Theorem ==
Let $m \in \R$.
Define:
The recursive sequence:
:$V_n = m V_{n - 1} + V_{n - 2}$
where:
has the closed-form solution:
:$V_n = \alpha^n + \beta^n$
where $\Delta, \alpha, \beta$ are as for the first form.
== Proof ==
Proof by induction:
Let $\map P n$ be the proposition:
:$V_n = \alpha^n + \beta^n$
=== Basis for the Induction ===
We have:
Therefore $\map P 0$ and $\map P 1$ are true.
This is the basis for the induction.
=== Induction Hypothesis ===
This is our induction hypothesis:
:For some $k \in \N$, both $\map P k$ and $\map P {k + 1}$ are true.
That is:
:$V_k = \alpha^k + \beta^k$
:$V_{k + 1} = \alpha^{k + 1} + \beta^{k + 1}$
Now we need to show true for $n = k + 2$:
:$\map P {k + 2}$ is true.
That is:
:$V_{k + 2} = \alpha^{k + 2} + \beta^{k + 2}$
=== Induction Step ===
This is our induction step:
First we notice that:
Similarly:
Thus:
This show that $\map P {k + 2}$ is true.
By principle of mathematical induction, $\map P n$ is true for all $n \in \N$.
Category:Binet Form
Bing's Metrization Theorem

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
Then:
:$T$ is metrizable $T$ is regular and has a $\sigma$-discrete basis
== Proof ==
== Historical Note ==
== Sources ==
* : Chapter $4$: Embedding and Metrization
* : Chapter $6$: Metrization Theorems and Paracompactness: $\S40$: The Nagata-Smirnov Metrization Theorem: Exrcise: $5$
* : Part $\text {III}$: Metrization Theory: Conjectures and Counterexamples: Screenable Spaces
Category:Metrization Theorems
Category:Regular Spaces
Category:Metrizable Topologies
Bing's Metrization Theorem/Historical Note

== Historical Note on Bing's Metrization Theorem ==
Bing's Metrization Theorem was discovered in $1951$ by , independently of the Nagata-Smirnov Metrization Theorem discovered by ($1950$) and ($1951$). 
The two theorems Bing's Metrization Theorem and Nagata-Smirnov Metrization Theorem are often merged as the Bing-Nagata-Smirnov Metrization Theorem.
Category:Historical Notes
Binomial Coefficient/Examples

== Examples of Binomial Coefficients==
=== $2$ from $5$ ===
=== $5$ from $2$ ===
=== $2$ from $-5$ ===
=== $5$ from $-2$ ===
=== $3$ from $7$ ===
=== $3$ from $8$ ===
=== $4$ from $9$ ===
=== $5$ from $12$ ===
=== $4$ from $52$ ===
=== Number of Bridge Hands ===
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/2 from -5

== Example of Binomial Coefficient ==
:$\dbinom {-5} 2 = 15$
== Proof ==
From the definition of binomial coefficient:
:$\dbinom r k = \begin {cases}
\dfrac {r^{\underline k} } {k!} & : k \ge 0 \\
& \\
0 & : k < 0
\end {cases}$
where $r^{\underline k}$ denotes the falling factorial.
Therefore:
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/3 from 7

== Example of Binomial Coefficient ==
The number of ways of choosing $3$ objects from a set of $7$ is:
:$\dbinom 7 3 = \dfrac {7 \times 6 \times 5} {3 \times 2 \times 1} = \dfrac {7!} {3! \, 4!} = 35$
== Sources ==
* : Problems
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/3 from 8

== Example of Binomial Coefficient ==
The number of ways of choosing $3$ objects from a set of $8$ is:
:$\dbinom 8 3 = \dfrac {8 \times 7 \times 6} {3 \times 2 \times 1} = \dfrac {8!} {3! \, 5!} = 56$
== Sources ==
* : Chapter $1$: Some Preliminary Considerations: $1.2$ The Binomial Theorem
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/4 from 52

== Example of Binomial Coefficient ==
The number of ways of choosing $4$ objects from a set of $52$ (for example, cards from a deck) is:
:$\dbinom {52} 4 = \dfrac {52 \times 51 \times 50 \times 49} {4 \times 3 \times 2 \times 1} = \dfrac {52!} {48! \, 4!} = 270 \, 725$
== Sources ==
* : $24$
* : $24$
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/4 from 9

== Example of Binomial Coefficient ==
The number of ways of choosing $4$ objects from a set of $9$ is:
:$\dbinom 9 4 = \dfrac {9 \times 8 \times 7 \times 6} {4 \times 3 \times 2 \times 1} = \dfrac {9!} {4! \, 5!} = 126$
== Sources ==
* : $\S 3$: The Binomial Formula and Binomial Coefficients: Binomial Coefficients: $3.5$: Example
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/5 from -2

== Example of Binomial Coefficient ==
:$\dbinom {-2} 5 = -6$
== Proof ==
From the definition of binomial coefficient:
:$\dbinom r k = \begin {cases}
\dfrac {r^{\underline k} } {k!} & : k \ge 0 \\
& \\
0 & : k < 0
\end {cases}$
where $r^{\underline k}$ denotes the falling factorial.
Therefore:
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/5 from 12

== Example of Binomial Coefficient ==
The number of ways of choosing $5$ objects from a set of $12$ is:
:$\dbinom {12} 5 = \dfrac {12 \times 11 \times 10 \times 9 \times 8} {5 \times 4 \times 3 \times 2 \times 1} = \dfrac {12!} {7! \, 5!} = 792$
== Sources ==
* : $\S 3$: The Binomial Formula and Binomial Coefficients: Binomial Coefficients: $3.5$: Example
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/5 from 2

== Example of Binomial Coefficient ==
:$\dbinom 2 5 = 0$
== Proof ==
From the definition of binomial coefficient:
:$\dbinom n k = \begin{cases}
\dfrac {n!} {k! \paren {n - k}!} & : 0 \le k \le n \\
& \\
0 & : \text { otherwise } \end{cases}$
Here we have $k = 5$ and $n = 2$.
As $k > n$:
:$\dbinom 2 5 = 0$
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/Number of Bridge Hands

== Theorem ==
The total number $N$ of possible different hands for a game of bridge is:
:$N = \dfrac {52!} {13! \, 39!} = 635 \ 013 \ 559 \ 600$
=== Prime Factors ===
== Proof ==
The total number of cards in a standard deck is $52$.
The number of cards in a single bridge hand is $13$.
Thus $N$ is equal to the number of ways $13$ things can be chosen from $52$.
Thus:
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $3$
Category:Examples of Binomial Coefficients‎
Binomial Coefficient/Examples/Number of Bridge Hands/Prime Factors

== Example of Factorial ==
The prime decomposition of the number of bridge hands is given as:
:$\dbinom {52} {13} = 2^4 \times 5^2 \times 7^2 \times 17 \times 23 \times 41 \times 43 \times 47$
== Proof ==
We have by definition of binomial coefficient:
:$\dbinom {52} {13} = \dfrac {52!} {13! \, 39!}$
Thus it is necessary to determine the prime factors of each of the contributing factorials here.
From Prime Factors of $52!$:
:$52! = 2^{49} \times 3^{23} \times 5^{12} \times 7^8 \times 11^4 \times 13^4 \times 17^3 \times 19^2 \times 23^2 \times 29 \times 31 \times 37 \times 41 \times 43 \times 47$
From Prime Factors of $39!$:
:$39! = 2^{35} \times 3^{18} \times 5^8 \times 7^5 \times 11^3 \times 13^3 \times 17^2 \times 19^2 \times 23 \times 29 \times 31 \times 37$
From Prime Factors of $13!$:
:$13! = 2^{10} \times 3^5 \times 5^2 \times 7 \times 11 \times 13$
For each prime factor $p$ of $\dbinom {52} {13}$, let $a_p$ be the integer such that:
:$p^{a_p} \divides \dbinom {52} {13}$
:$p^{a_p + 1} \nmid \dbinom {52} {13}$
Taking the prime factors in turn:
Finally:
:$a_{41} = a_{43} = a_{47} = 1$
Hence the result.
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $4$
Category:Examples of Binomial Coefficients‎
Binomial Coefficient 2 n Choose n is Divisible by All Primes between n and 2 n

== Theorem ==
Let $\dbinom {2 n} n$ denote a binomial coefficient.
Then for all prime numbers $p$ such that $n < p < 2 n$:
:$p \divides \dbinom {2 n} n$
where $\divides$ denotes divisibility.
== Proof ==
By definition of binomial coefficient:
Let $\mathbb P$ denote the set of prime numbers.
Let $p \in \mathbb P$ such that $n < p < 2 n$.
By definition of factorial:
:$p \divides \paren {2 n}!$
That is:
:$p \divides \dbinom {2 n} n \paren {n!}^2$
From Prime iff Coprime to all Smaller Positive Integers:
:$p \nmid n!$
where $\nmid$ denotes non-divisibility.
and so:
:$p \nmid \paren {n!}^2$
But from Euclid's Lemma for Prime Divisors, $p$ is a divisor of either $\dbinom {2 n} n$ or $\paren {n!}^2$.
Hence it must be the case that:
:$p \divides \dbinom {2 n} n$
== Sources ==
* : Chapter $2$: Integers and natural numbers: $\S 2.2$: Divisibility and factorization in $\mathbf Z$: Exercise $3$
Category:Binomial Coefficients
Binomial Coefficient expressed using Beta Function

== Theorem ==
Let $\dbinom r k$ denote a binomial coefficient.
Then:
:$\dbinom r k = \dfrac 1 {\paren {r + 1} \map B {k + 1, r - k + 1} }$
== Proof ==
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $42$
Category:Beta Function
Category:Binomial Coefficients
Binomial Coefficient involving Power of Prime

== Theorem ==
Let $p$ be a prime number.
Let $k \in \Z$.
Let $n \in \Z_{>0}$.
Then:
: $\dbinom {p^n k} {p^n} \equiv k \pmod p$
where $\dbinom {p^n k} {p^n}$ is a binomial coefficient.
== Proof 1 ==
== Proof 2 ==
Category:Prime Numbers
Category:Binomial Coefficients
Category:Binomial Coefficient involving Power of Prime
Binomial Coefficient involving Power of Prime/Proof 1

== Theorem ==
== Proof ==
From Prime Power of Sum Modulo Prime we have:
:$(1): \quad \paren {a + b}^{p^n} \equiv \paren {a^{p^n} + b^{p^n} } \pmod p$
We can write this:
:$\paren {a + b}^{p^n k} = \paren {\paren {a + b}^{p^n} }^k$
By $(1)$ and Congruence of Powers, we therefore have:
:$\paren {a + b}^{p^n k} \equiv \paren {a^{p^n} + b^{p^n} }^k \pmod p$
The coefficient $\dbinom {p^n k} {p^n}$ is the binomial coefficient of $b^{p^n}$ in $\paren {a + b}^{p^n k} = \paren {\paren {a + b}^{p^n} }^k$.
Expanding $\paren {a^{p^n} + b^{p^n} }^k$ using the Binomial Theorem, we find that the coefficient of $b^{p^n}$, the second term, is $\dbinom k 1 = k$.
So:
:$\dbinom {p^n k} {p^n} \equiv k \pmod p$
== Sources ==
* : $\S 2.6$. Algebra of congruences: Example $42 \ (5)$
* : Chapter $11$: The Sylow Theorems: Lemma $11.2$
Category:Binomial Coefficient involving Power of Prime
Binomial Coefficient involving Power of Prime/Proof 2

== Theorem ==
== Proof ==
Lucas' Theorem states that for $n, k, p \in \Z$ and $p$ be a prime number, such that:
:$n = a_r p^r + \cdots + a_1 p + a_0$
:$k = b_r p^r + \cdots + b_1 p + b_0$
then:
:$\ds \binom n k \equiv \prod_{j \mathop = 0}^r \binom {a_j}{b_j} \pmod p$
Therefore:
Category:Binomial Coefficient involving Power of Prime
Binomial Coefficient involving Prime

== Theorem ==
Let $p$ be a prime number.
Let $\dbinom n p$ be a binomial coefficient.
Then:
:$\dbinom n p \equiv \floor {\dfrac n p} \pmod p$
where:
:$\floor {\dfrac n p}$
denotes the floor function.
== Proof ==
Follows directly from Lucas' Theorem:
:$\dbinom n k \equiv \dbinom {\floor {n / p} } {\floor {k / p} } \dbinom {n \bmod p} {k \bmod p} \pmod p$
where $k = p$.
Then:
:$k \bmod p = 0$
and so by Binomial Coefficient with Zero:
:$\dbinom {n \bmod p} {k \bmod p} = 1$
Also:
:$\floor {k / p} = 1$
and by Binomial Coefficient with One:
:$\dbinom {\floor {n / p} } {\floor {k / p} } = \floor {\dfrac n p}$
Thus:
:$\dbinom n p \equiv \floor {\dfrac n p} \times 1 \pmod p$
Hence the result.
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $10 \ \text{(a)}$
Category:Binomial Coefficients
Binomial Coefficient is Integer/Proof 1

== Theorem ==
== Proof ==
If it is not the case that $0 \le k \le n$, then the result holds trivially.
So let $0 \le k \le n$.
By the definition of binomial coefficients:
The numerator is a product of $k$ successive integers.
From Factorial Divides Product of Successive Numbers, $k!$ divides it.
Category:Binomial Coefficient is Integer
Binomial Coefficient is instance of Gaussian Binomial Coefficient

== Theorem ==
Let $\dbinom r m_q$ denote the Gaussian binomial coefficient:
Then:
:$\ds \lim_{q \mathop \to 1^-} \dbinom r m_q = \dbinom r m$
where $\dbinom r m$ denotes the conventional binomial coefficient.
== Proof ==
We have by definition of Gaussian binomial coefficient:
:$\ds \dbinom r m_q = \prod_{k \mathop = 0}^{m - 1} \dfrac {1 - q^{r - k} } {1 - q^{k + 1} }$
Consider a typical factor of this continued product:
Thus:
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients
Category:Binomial Coefficients
Binomial Coefficient n Choose j in terms of n-2 Choose r

== Theorem ==
Let $n \in \Z$ such that $n \ge 4$.
Let $\dbinom n k$ denote a binomial coefficient for $k \in \Z$.
Then:
:$\dbinom n k = \dbinom {n - 2} {k - 2} + 2 \dbinom {n - 2} {k - 1} + \dbinom {n - 2} k$
for $2 \le k \le n - 2$.
== Proof ==
In the expression $\dbinom {n - 2} {k - 2} + 2 \dbinom {n - 2} {k - 1} + \dbinom {n - 2} k$ we note that:
:if $k < 2$ then $\dbinom {n - 2} {k - 2}$ has a negative coefficient on the bottom
:if $k > n - 2$ then $\dbinom {n - 2} k$ has a coefficient on the bottom that is greater than $n$.
Hence the usual comfortable range of $k$ is exceeded and so it cannot be guaranteed that the conditions are satisfied for the equation to be true.
If $n \le 3$ then $2 \le k \le n - 2$ cannot be fulfilled.
Hence the bounds on both $k$ and $n$.
== Sources ==
* : Chapter $1$: Some Preliminary Considerations: $1.2$ The Binomial Theorem: Problems $1.2$: $2$
Category:Binomial Coefficients
Binomial Coefficient n Choose k by n Plus 1 Minus n Choose k + 1

== Theorem ==
Let $\sequence {A_{n k} }$ be a sequence defined on $n, k \in \Z_{\ge 0}$ as:
:$A_{n k} = \begin{cases} 1 & : k = 0 \\
0 & : k \ne 0, n = 0 \\
A_{\paren {n - 1} k} + A_{\paren {n - 1} \paren {k - 1} } + \dbinom n k & : \text{otherwise}
\end{cases}$
Then the closed form for $A_{n k}$ is given as:
:$A_{n k} = \paren {n + 1} \dbinom n k - \dbinom n {k + 1}$
== Proof ==
The proof proceeds by induction on $n$.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$A_{n k} = \paren {n + 1} \dbinom n k - \dbinom n {k + 1} + \dbinom n k$
=== Basis for the Induction ===
$\map P 0$ is the case $A_{0 k}$:
Let $k = 0$.
Then:
Let $k > 0$.
Then:
Thus $\map P 0$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P r$ is true, where $r \ge 0$, then it logically follows that $\map P {r + 1}$ is true.
So this is the induction hypothesis:
:$A_{r k} = \paren {r + 1} \dbinom r k - \dbinom r {k + 1}$
from which it is to be shown that:
:$A_{\paren {r + 1} k} = \paren {r + 2} \dbinom {r + 1} k - \dbinom {r + 1} {k + 1}$
=== Induction Step ===
This is the induction step:
So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n, k \in \Z_{\ge 0}: A_{n k} = \paren {n + 1} \dbinom n k - \dbinom n {k + 1}$
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $59$
Category:Binomial Coefficients
Binomial Coefficient of Half

== Theorem ==
Let $k \in \Z$.
:$\dbinom {\frac 1 2} k = \dfrac {\left({-1}\right)^{k - 1} } {4^k \left({2 k - 1}\right)} \dbinom {2 k} k$
where $\dbinom {\frac 1 2} k$ denotes a binomial coefficient.
=== Corollary ===
== Proof ==
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $53 \ \text{(b)}$
Category:Examples of Binomial Coefficients
Binomial Coefficient of Half/Corollary

== Theorem ==
Let $k \in \Z_{\ge 0}$.
:$\dbinom {\frac 1 2} k = \dfrac {\paren {-1}^{k - 1} } {2^{2 k - 1} \paren {2 k - 1} } \dbinom {2 k - 1} k - \delta_{k 0}$
where:
:$\dbinom {\frac 1 2} k$ denotes a binomial coefficient
:$\delta_{k 0}$ denotes the Kronecker delta.
== Proof ==
When $k > 0$ we have:
When $k = 0$ we have:
while:
Hence:
:$(1): \quad \dbinom {\frac 1 2} k = \dfrac {2 \paren {-1}^{k - 1} } {4^k \paren {2 k - 1} } \dbinom {2 k - 1} k - \delta_{k 0}$
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $53 \ \text{(b)}$
Category:Examples of Binomial Coefficients
Binomial Coefficient of Minus Half

== Theorem ==
Let $k \in \Z$.
:$\dbinom {-\frac 1 2} k = \dfrac {\paren {-1}^k} {4^k} \dbinom {2 k} k$
where $\dbinom {-\frac 1 2} k$ denotes a binomial coefficient.
== Proof ==
From Product of r Choose k with r Minus Half Choose k:
:$\dbinom r k \dbinom {r - \frac 1 2} k = \dfrac {\dbinom {2 r} k \dbinom {2 r - k} k} {4^k}$
Setting $r = -\dfrac 1 2$:
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $47$
* : $\S 1.2.6$: Binomial Coefficients: Exercise $53 \ \text{(b)}$
Category:Examples of Binomial Coefficients
Binomial Coefficient of Prime

== Theorem ==
Let $p$ be a prime number.
Then:
:$\forall k \in \Z: 0 < k < p: \dbinom p k \equiv 0 \pmod p$
where $\dbinom p k$ is defined as a binomial coefficient.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Sources ==
* : $\text {3-1}$ Permutations and Combinations: Exercise $9$
* : $\S 2.3$: Congruences: Exercise $8$
* : $35$
* : $\S 2.1$: Exercise $45$
* : $35$
Category:Binomial Coefficient of Prime
Category:Prime Numbers
Category:Binomial Coefficients
Binomial Coefficient of Prime/Proof 1

== Theorem ==
== Proof ==
Because:
:$\dbinom p k = \dfrac {p \paren {p - 1} \paren {p - 2} \cdots \paren {p - k + 1} } {k!}$
is an integer, we have that:
:$k! \divides p \paren {p - 1} \paren {p - 2} \cdots \paren {p - k + 1}$
But because $k < p$ it follows that:
:$k! \mathrel \perp p$
that is, that:
:$\gcd \set {k!, p} = 1$
So by Euclid's Lemma:
:$k! \divides \paren {p - 1} \paren {p - 2} \cdots \paren {p - k + 1}$
Hence:
:$\dbinom p k = p \dfrac {\paren {p - 1} \paren {p - 2} \cdots \paren {p - k + 1} } {k!}$
Hence the result.
Category:Binomial Coefficient of Prime
Binomial Coefficient of Prime/Proof 2

== Theorem ==
== Proof ==
Lucas' Theorem gives:
:$\dbinom n k \equiv \dbinom {\left \lfloor {n / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \dbinom {n \bmod p} {k \bmod p} \pmod p$
So, substituting $p$ for $n$:
:$\dbinom p k \equiv \dbinom {\left \lfloor {p / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \dbinom {p \bmod p} {k \bmod p} \pmod p$
But $p \bmod p = 0$ by definition.
Hence, if $0 < k < p$, we have that:
:$k \bmod p \ne 0$
and so:
:$\dbinom {p \bmod p} {k \bmod p} = \dbinom 0 {k \bmod p} = 0$
by definition of binomial coefficients.
The result follows immediately.
== Sources ==
* : $\S 1.2.6$: Binomial Coefficients: Exercise $10 \ \text{(b)}$
Category:Binomial Coefficient of Prime
Binomial Coefficient of Prime/Proof 3

== Theorem ==
== Proof ==
By the definition of binomial coefficient:
Now, $p$ divides the by Divisors of Factorial.
So $p$ must also divide the .
By hypothesis $k < p$.
We have that:
:$k! = k \paren {k - 1} \dotsm \paren 2 \paren 1$
We also have that $p$ is prime, and each factor is less than $p$.
Thus $p$ is not a factor of $k!$.
Similarly:
:$\paren {p - k}! = \paren {p - k} \paren {p - k - 1} \dotsm \paren 2 \paren 1$
It follows, by the same reasoning as above, that $p$ is also not a factor of $\paren {p - k}!$.
The result then follows from Euclid's Lemma.
Category:Binomial Coefficient of Prime