avewright/proofwiki-math huggingface dataset:
Theorem: Intersection of Applications of Down Mappings at Element equals Way Below Closure of Element

Let $L = \struct {S, \vee, \wedge, \preceq}$ be a bounded below meet-continuous lattice.
Let $\operatorname {Ids}$ be the set of all ideals in $L$.
Let for all $I \in \operatorname {Ids}$: $m_I: S \to \operatorname {Ids}$ be a mapping:
:$\forall x \in S: x \preceq \sup I \implies \map {m_I} x = \set {x \wedge i: i \in I}$
and
:$\forall x \in S: x \npreceq \sup I \implies \map {m_I} x = x^\preceq$
where $x^\preceq$ denotes the lower closure of $x$.
Let $x \in S$.
Then
:$\ds \bigcap \set {\map {m_I} x: I \in \operatorname {Ids} } = x^\ll$
where $x^\ll$ denotes the way below closure of $x$.

Proof:
{{begin-eqn}}
{{eqn | l = \set {\map {m_I} x: I \in \operatorname {Ids} }
      | r = \set {\map {m_I} x: I \in \operatorname {Ids} \land x \preceq \sup I} \cup \set {\map {m_I} x: I \in \operatorname {Ids} \land x \npreceq \sup I}
}}
{{eqn | r = \set {\set {x \wedge i: i \in I}: I \in \operatorname {Ids} \land x \preceq \sup I} \cup \set {x^\preceq: I \in \operatorname {Ids} \land x \npreceq \sup I}
      | c = Definition of $m_I$
}}
{{eqn | r = \set {\paren {x^\preceq} \cap I: I \in \operatorname {Ids} \land x \preceq \sup I} \cup \set {x^\preceq: I \in \operatorname {Ids} \land x \npreceq \sup I}
      | c = Intersection of Lower Closure of Element with Ideal equals Meet of Element and Ideal
}}
{{end-eqn}}
Thus
{{begin-eqn}}
{{eqn | l = \bigcap \set {\map {m_I} x: I \in \operatorname {Ids} }
      | r = \bigcap \set {\paren {x^\preceq} \cap I: I \in \operatorname {Ids} \land x \preceq \sup I} \cap \bigcap \set {x^\preceq: I \in \operatorname {Ids} \land x \npreceq \sup I}
      | c = 
}}
{{eqn | r = \bigcap \set {\paren {x^\preceq} \cap I: I \in \operatorname {Ids} \land x \preceq \sup I} \cap \bigcap \set {x^\preceq}
}}
{{eqn | r = \bigcap \set {\paren {x^\preceq} \cap I: I \in \operatorname {Ids} \land x \preceq \sup I} \cap x^\preceq
      | c = Intersection of Singleton
}}
{{eqn | r = \paren {x^\preceq} \cap \bigcap \set {I: I \in \operatorname {Ids} \land x \preceq \sup I} \cap x^\preceq
      | c = Set Intersection is Self-Distributive
}}
{{eqn | r = \paren {x^\preceq} \cap \paren {x^\ll} \cap x^\preceq
      | c = Intersection of Ideals with Suprema Succeed Element equals Way Below Closure of Element
}}
{{eqn | r = x^\ll
      | c = Intersection with Subset is Subset as $x^\ll \subseteq x^\preceq$ by Way Below implies Preceding
}}
{{end-eqn}}
{{qed}}
Theorem: Sum over k to n of Stirling Number of the Second Kind of k with m by m+1^n-k

Let $m, n \in \Z_{\ge 0}$.
:$\ds \sum_{k \mathop \le n} {k \brace m} \paren {m + 1}^{n - k} = {n + 1 \brace m + 1}$
where $\ds {k \brace m}$ etc. denotes a Stirling number of the second kind.

Proof:
The proof proceeds by induction on $n$.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\ds \forall n \in \Z_{\ge 0}: \sum_{k \mathop \le n} {k \brace m} \paren {m + 1}^{n - k} = {n + 1 \brace m + 1}$
Theorem: Zero Choose Zero

:$\dbinom 0 0 = 1$

Proof:
By Zero Choose n:
:$\dbinom 0 n = \delta_{0 n}$
where:
:$\dbinom 0 n$ denotes a binomial coefficient
:$\delta_{0 n}$ denotes the Kronecker delta.
Hence directly:
:$\dbinom 0 0 = 1$
Theorem: Zero Choose Zero

:$\dbinom 0 0 = 1$

Proof:
By Binomial Coefficient with Zero:
:$\forall r \in \R: \dbinom r 0 = 1$
Hence directly:
:$\dbinom 0 0 = 1$
Theorem: Binomial Coefficient/Examples/Number of Bridge Hands

The total number $N$ of possible different hands for a game of [https://en.wikipedia.org/wiki/Contract_bridge bridge] is:
:$N = \dfrac {52!} {13! \, 39!} = 635 \ 013 \ 559 \ 600$

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:
{{begin-eqn}}
{{eqn | l = N
      | r = \dbinom {52} {23}
      | c = Cardinality of Set of Subsets
}}
{{eqn | r = \frac {52!} {13! \left({52 - 13}\right)!}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = \frac {52!} {13! \, 39!}
      | c = 
}}
{{eqn | r = 635 \ 013 \ 559 \ 600
      | c = after calculation
}}
{{end-eqn}}
{{qed}}
Theorem: Intersection of Lower Closure of Element with Ideal equals Meet of Element and Ideal

Let $\struct {S, \preceq}$ be a meet semilattice.
Let $I$ be an ideal in $\struct {S, \preceq}$.
Let $x \in S$.
Then:
:$\paren {x^\preceq} \cap I = \set {x \wedge i: i \in I}$
where $x^\preceq$ denotes the lower closure of $x$.

Proof:
=== First Inclusion ===
Let $z \in \paren {x^\preceq} \cap I$
By definition of intersection:
:$z \in x^\preceq$ and $z \in I$
By definition of lower closure of element:
:$z \preceq x$
By Preceding iff Meet equals Less Operand:
:$x \wedge z = z$
Thus:
:$z \in \set {x \wedge i: i \in I}$
{{qed|lemma}}
Theorem: Condition on Lower Coefficient for Binomial Coefficient to be Maximum

Let $n, k \in \Z_{\ge 0}$ be positive integers.
Let $\dbinom n k$ denote the binomial coefficient of $n$ choose $k$.
Then for a given value of $n$, the value of $k$ for which $\dbinom n k$ is a maximum is:
:$k_\max = \floor {\dfrac n 2}$
and also:
:$k_\max = \ceiling {\dfrac n 2}$

Proof:
From Condition for Increasing Binomial Coefficients:
:$\forall k \in \Z_{> 0}: \dbinom n k > \dbinom n {k - 1} \iff k \le \dfrac n 2$
Let $n$ be an even integer, such that:
:$n = 2 r$
Then:
:$r = \floor {\dfrac n 2} = \ceiling {\dfrac n 2}$
and:
:$\forall k < r: \dbinom n r > \dbinom n k$
From Symmetry Rule for Binomial Coefficients:
:$\forall k < r: \dbinom n r > \dbinom n {n - k}$
and so:
:$\forall k > r: \dbinom n r > \dbinom n k$
We also have:
:$\dbinom n r = \dbinom n {n - r} = \dbinom n {n / 2}$
Thus for all $k \ne r$:
:$\dbinom n k < \dbinom n {n / 2}$
and so:
:$k_\max = \floor {\dfrac n 2} = \ceiling {\dfrac n 2}$
{{qed|lemma}}
Let $n$ be an odd integer, such that:
:$n = 2 r + 1$
Then:
:$r = \floor {\dfrac n 2}$
As $r < n$:
:$\forall k < r: \dbinom n r > \dbinom n k$
When $k = r$ we also have:
:$\dbinom n r = \dbinom n {n - r} = \dbinom n {r + 1}$
Then from Symmetry Rule for Binomial Coefficients:
:$\forall k < r: \dbinom n r > \dbinom n {n - k}$
and so:
:$\forall k > r + 1: \dbinom n r > \dbinom n k$
We have that:
:$r = \floor {\dfrac n 2}$
and:
:$r + 1 = \ceiling {\dfrac n 2}$
Hence the result.
{{qed}}
Theorem: Row in Pascal's Triangle forms Palindromic Sequence

Each of the rows of Pascal's triangle forms a palindromic sequence.

Proof:
The $n$th row of Pascal's triangle consists of the finite sequence:
:$\dbinom n 0, \dbinom n 1, \dbinom n 2, \ldots, \dbinom n {n - 2}, \dbinom n {n - 1}, \dbinom n n$
By the Symmetry Rule for Binomial Coefficients:
:$\dbinom n m = \dbinom n {n - m}$
Hence we can write the $n$th row in reverse order:
{{begin-eqn}}
{{eqn | o = 
      | r = \dbinom n n, \dbinom n {n - 1}, \dbinom n {n - 2}, \ldots, \dbinom n 2, \dbinom n 1, \dbinom n 0
      | c = 
}}
{{eqn | r = \dbinom n {n - n}, \dbinom n {n - \left({n - 1}\right)}, \dbinom n {n - \left({n - 2}\right)}, \ldots, \dbinom n {n - 2}, \dbinom n {n - 1}, \dbinom n {n - 0}
      | c = 
}}
{{eqn | r = \dbinom n 0, \dbinom n 1, \dbinom n 2, \ldots, \dbinom n {n - 2}, \dbinom n {n - 1}, \dbinom n n
      | c = 
}}
{{end-eqn}}
and the sequences are seen to be the same.
{{qed}}
Theorem: N Choose Negative Number is Zero

Let $n \in \Z$ be an integer.
Let $k \in \Z_{<0}$ be a (strictly) negative integer.
Then:
:$\dbinom n k = 0$

Proof:
From Pascal's Rule we have:
:$\forall n, k \in \Z: \dbinom n {k - 1} = \dbinom {n + 1} k - \dbinom n k$
Thus it is sufficient to prove that:
:$\forall n \in \Z: \dbinom n {-1} = 0$
So:
{{begin-eqn}}
{{eqn | l = \dbinom n {-1}
      | r = \dbinom {n + 1} 0 - \dbinom n 0
      | c = Pascal's Rule
}}
{{eqn | r = 1 - 1
      | c = Binomial Coefficient with Zero
}}
{{eqn | r = 0
      | c = 
}}
{{end-eqn}}
Hence the result.
{{qed}}
Category:Binomial Coefficients
jilju9t3idp64zejhlfrap6ma23dwna
Theorem: Kummer's Theorem

Let $p$ be a prime number.
Let $a, b \in \Z_{\ge 0}$.
Let:
:$p^n \divides \dbinom {a + b} b$
but
:$p^{n + 1} \nmid \dbinom {a + b} b$
where:
:$\divides$ denotes divisibility
:$\nmid$ denotes non-divisibility
:$\dbinom {a + b} b$ denotes a binomial coefficient.
Then $n$ equals the number of carries that occur when $a$ is added to $b$ using the classical addition algorithm in base $p$.

Proof:
{{ProofWanted|We need to establish the classical algorithms and build up the knowledge of exactly what a carry is before tackling this delightful little number.}}
{{Namedfor|Ernst Eduard Kummer|cat = Kummer}}
Theorem: Numbers in Row of Pascal's Triangle all Odd iff Row number 2^n - 1

Let $n \in \Z_{\ge 0}$ be a positive integer.
Then the non-zero elements of the $n$th row of Pascal's triangle are all odd {{iff}}:
:$n = 2^m - 1$
for some $m \in \Z_{\ge 0}$.
{{:Definition:Pascal's Triangle}}
As can be seen, the entries in rows $0, 1, 3, 7$ are all odd.

Proof:
The statement:
:$\dbinom n k$ is odd
is equivalent to:
:$\dbinom n k \equiv 1 \pmod p$
{{Corollary|Lucas' Theorem}} gives:
:$\ds \dbinom n k \equiv \prod_{j \mathop = 0}^r \dbinom {a_j} {b_j} \pmod p$
where:
:$n, k \in \Z_{\ge 0}$ and $p$ is prime
:the representations of $n$ and $k$ to the base $p$ are given by:
::$n = a_r p^r + \cdots + a_1 p + a_0$
::$k = b_r p^r + \cdots + b_1 p + b_0$
When $p = 2$, the digits $a_j, b_j$ are either $0$ or $1$.
In order for $\dbinom n k \equiv 1 \pmod p$, it is necessary and sufficient that $\dbinom {a_j} {b_j} \equiv 1 \pmod p$ for all $j \in \set {0, 1, 2, \ldots, r}$.
In order for this to happen, either:
:$\dbinom {a_j} {b_j} = \dbinom 0 0$
or:
:$\dbinom {a_j} {b_j} = \dbinom 1 0$
or:
:$\dbinom {a_j} {b_j} = \dbinom 1 1$
Suppose $a_i = 0$ for some $i \in \set {0, 1, 2, \ldots, r}$.
Then if $b_i = 1$:
:$\dbinom {a_j} {b_j} = \dbinom 0 1 = 0$
and so:
:$\dbinom n k \equiv 0 \pmod p$
for whichever $k$ (and there will be at least one) has digit $b_i = 1$.
So the only way it can be assured that all $\dbinom {a_j} {b_j} \equiv 1 \pmod p$ for all $k \in \set {0, 1, 2, \ldots, n}$ is for $a_j = 0$ for all $j \in \set {0, 1, 2, \ldots, r}$.
That is, for $n = 2^m - 1$ for some $m \in \Z_{\ge 0}$.
{{qed}}
Theorem: Sum of Sequence of Fourth Powers

:$\ds \sum_{k \mathop = 0}^n k^4 = \dfrac {\paren {n + 1} n \paren {n + \frac 1 2} \paren {3 n^2 + 3 n - 1} } {15}$

Proof:
From Faulhaber's Formula:
{{begin-eqn}}
{{eqn | l = \sum_{i \mathop = 1}^n i^p
      | r = 1^p + 2^p + \cdots + n^p
      | c = 
}}
{{eqn | r = \frac {n^{p + 1} } {p + 1} + \sum_{k \mathop = 1}^p \frac {B_k \, p^{\underline {k - 1} } \, n^{p - k + 1} } {k!}
      | c = 
}}
{{end-eqn}}
where $B_k$ are the Bernoulli numbers.
Setting $p = 4$:
{{begin-eqn}}
{{eqn | l = \sum_{i \mathop = 1}^n i^4
      | r = \frac {n^{4 + 1} } {4 + 1} + \sum_{k \mathop = 1}^4 \frac {B_k \, 4^{\underline {k - 1} } \, n^{4 - k + 1} } {k!}
      | c = 
}}
{{eqn | r = \frac {n^5} 5 + \frac {B_1 \, 4^{\underline 0} \, n^4} {1!} + \frac {B_2 \, 4^{\underline 1} \, n^3} {2!} + \frac {B_3 \, 4^{\underline 2} \, n^2} {3!} + \frac {B_4 \, 4^{\underline 3} \, n} {4!}
      | c = 
}}
{{eqn | r = \frac {n^5} 5 + \frac 1 2 \frac {n^4} {1!} + \frac 1 6 \frac {4 n^3} {2!} + 0 \frac {4 \times 3 n^2} {3!} - \frac 1 {30} \frac {4 \times 3 \times 2 n} {4!}
      | c = {{Defof|Bernoulli Numbers}} and {{Defof|Falling Factorial}}
}}
{{eqn | r = \frac {n^5} 5 + \frac {n^4} 2 + \frac {n^3} 3 - \frac n {30}
      | c = simplifying
}}
{{eqn | r = \frac {6 n^5 + 15 n^4 + 10 n^3 - n} {30}
      | c = 
}}
{{eqn | r = \frac {n \paren {n + 1} \paren {2 n + 1} \paren {3 n^2 + 3 n - 1} } {30}
      | c = 
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Sum of Sequence of Fourth Powers

:$\ds \sum_{k \mathop = 0}^n k^4 = \dfrac {\paren {n + 1} n \paren {n + \frac 1 2} \paren {3 n^2 + 3 n - 1} } {15}$

Proof:
By definition of binomial coefficient:
{{begin-eqn}}
{{eqn | l = \binom k 4
      | r = \frac {k \paren {k - 1} \paren {k - 2} \paren {k - 3} } {4 !}
      | c = 
}}
{{eqn | l = \binom k 3
      | r = \frac {k \paren {k - 1} \paren {k - 2} } {3 !}
      | c = 
}}
{{eqn | l = \binom k 2
      | r = \frac {k \paren {k - 1} } {2 !}
      | c = 
}}
{{eqn | l = \binom k 1
      | r = k 
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 24 \binom k 4
      | r = k^4 - 6 k^3 + 11 k^2 - 6 k
      | c = 
}}
{{eqn | l = 36 \binom k 3
      | r = 6 k^3 - 18 k^2 + 12 k
      | c = 
}}
{{eqn | l = 14 \binom k 2
      | r = 7 k^2 - 7 k
      | c = 
}}
{{eqn | ll= \leadsto
      | l = k^4
      | r = 24 \binom k 4 + 36 \binom k 3 + 14 \binom k 2 + \binom k 1
      | c = 
}}
{{end-eqn}}
So:
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop = 0}^n k^4
      | r = \sum_{k \mathop = 0}^n \paren {24 \binom k 4 + 36 \binom k 3 + 14 \binom k 2 + \binom k 1}
      | c = 
}}
{{eqn | r = 24 \binom {n + 1} 5 + 36 \binom {n + 1} 4 + 14 \binom {n + 1} 3 + \binom {n + 1} 2
      | c = Sum of Binomial Coefficients over Upper Index
}}
{{eqn | r = 24 \frac {\paren {n + 1} n \paren {n - 1} \paren {n - 2} \paren {n - 3} } {5 !}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | o = 
      | ro= +
      | r = 36 \frac {\paren {n + 1} n \paren {n - 1} \paren {n - 2} } {4 !}
      | c = 
}}
{{eqn | o = 
      | ro= +
      | r = 14 \frac {\paren {n + 1} n \paren {n - 1} } {3 !}
      | c = 
}}
{{eqn | o = 
      | ro= +
      | r = \frac {\paren {n + 1} n } {2 !}
      | c = 
}}
{{eqn | r = \paren {n + 1} n \paren {\frac {\paren {n - 1} \paren {n - 2} \paren {n - 3} } 5 + \frac {3 \paren {n - 1} \paren {n - 2} } 2 + \frac {7 \paren {n - 1} } 3 + \frac 1 2}
      | c = 
}}
{{eqn | r = \frac {\paren {n + 1} n} {30} \paren {6 \paren {n^3 - 6 n^2 + 11 n - 6 } + 45 \paren {n^2 - 3 n + 2} + 70 \paren {n - 1} + 15}
      | c = 
}}
{{eqn | r = \frac {\paren {n + 1} n} {30} \paren {6 n^3 - 36 n^2 + 66 n - 36 + 45 n^2 - 135 n + 90 + 70 n - 70 + 15}
      | c = 
}}
{{eqn | r = \frac {\paren {n + 1} n} {30} \paren {6 n^3 + 9 n^2 + n - 1}
      | c = 
}}
{{eqn | r = \frac {\paren {n + 1} n} {30} \paren {2 n + 1} \paren {3 n^2 + 3 n - 1}
      | c = 
}}
{{eqn | r = \frac {\paren {n + 1} n \paren {n + \frac 1 2} \paren {3 n^2 + 3 n - 1} } {15}
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Complete Lattice is Bounded

Let $L = \struct {S, \vee, \wedge, \preceq}$ be a complete lattice.
Then
:$L$ is bounded.

Proof:
By definition of complete lattice:
:$\O$ admits a supremum and an infimum.
By Infimum of Empty Set is Greatest Element:
:$\forall x \in S: x \preceq \inf \O$
Thus by definition:
:$L$ is bounded above.
By Supremum of Empty Set is Smallest Element:
:$\forall x \in S: \sup \O \preceq x$
Thus by definition:
:$L$ is bounded below.
Hence $L$ is bounded.
{{qed}}
Theorem: Constant Function is Primitive Recursive/General Case

The constant function of $k$ variables: $f_c^k: \N^k \to \N$, defined as:
:$\map {f_c^k} {n_1, n_2, \ldots, n_k} = c$ where $c \in \N$
is primitive recursive.

Proof:
For $k \ge 1$, let $f_c^k$ be the constant function of $k$ variables with value $c$.
We know from Constant Function is Primitive Recursive that $f_c^1$ is primitive recursive.
Now:
:$\map {f_c^k} {n_1, n_2, \ldots, n_k} = \map {f_c^1} {n_1} = \map {f_c^1} {\map {\pr_1^k} {n_1, n_2, \ldots, n_k} }$
where $\pr_1^k$ is a projection function which is basic primitive recursive.
So $f_c^k$ is obtained from the primitive recursive function $f_c^1$ and the basic primitive recursive function $\pr_1^k$ by substitution.
Hence by definition, $f_c^k$ is primitive recursive.
{{qed}}
Category:Primitive Recursive Functions
Category:Constant Mappings
p7103pmh89wjmd8e0mfrg551rg2r1jz
Theorem: Value of Multiplicative Function at One

Let $f: \N \to \C$ be a multiplicative function.
If $f$ is not identically zero, then $\map f 1 = 1$.

Proof:
If $f$ is not identically zero, then:
:$\exists m \in \Z: \map f m \ne 0$
Then:
:$\map f m = \map f {1 \times m} = \map f 1 \, \map f m$
Hence $\map f 1 = 1$.
{{qed}}
Category:Multiplicative Functions
3yg93q06vyrng6lsj376wzn4zqpmn45
Theorem: Value of Multiplicative Function is Product of Values of Prime Power Factors

Let $f: \N \to \C$ be a multiplicative function.
Let $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$ be the prime decomposition of $n$.
Then:
:$\map f n = \map f {p_1^{k_1} } \, \map f {p_2^{k_2} } \dotsm \map f {p_r^{k_r} }$

Proof:
We have:
:$n = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}$
We also have:
:$\forall i, j \in \closedint 1 n: i \ne j \implies p_i^{k_i} \perp p_j^{k_j}$
So:
:$\map f {p_i^{k_i} p_j^{k_j} } = \map f {p_i^{k_i} } \, \map f {p_j^{k_j} }$
It is a simple inductive process to show that $\map f n = \map f {p_1^{k_1} } \, \map f {p_2^{k_2} } \dotsm \map f {p_r^{k_r} }$.
{{handwaving}}
{{qed}}
Category:Multiplicative Functions
2wrphk1b2zl7ohc8fzbupknu3hs00xb
Theorem: -1^n by -n choose k-1 equals -1^k by -k choose n-1

:$\paren {-1}^n \dbinom {-n} {k - 1} = \paren {-1}^k \dbinom {-k} {n - 1}$

Proof:
{{begin-eqn}}
{{eqn | l = \paren {-1}^n \dbinom {-n} {k - 1}
      | r = \paren {-1}^n \paren {\paren {-1}^{-n - \paren {k - 1} } \binom {-\paren {k - 1 + 1} } {-n - \paren {k - 1} } }
      | c = Moving Top Index to Bottom in Binomial Coefficient
}}
{{eqn | r = \paren {-1}^{- \paren {k - 1} } \binom {-k} {-\paren {n - 1} - k}
      | c = 
}}
{{eqn | r = \paren {-1}^k \binom {-k} {-k - \paren {n - 1} }
      | c = 
}}
{{eqn | r = \paren {-1}^k \binom {-k} {n - 1}
      | c = Symmetry Rule for Binomial Coefficients
}}
{{end-eqn}}
{{questionable|Can someone explain the disappearance of a factor of $-1$? Seems to have to do with a negative bottom index}}
Theorem: One Choose n

:$\dbinom 1 n = \begin{cases} 1 & : n \in \set {0, 1} \\ 0 & : \text {otherwise} \end{cases}$

Proof:
By definition of binomial coefficient:
:<nowiki>$\dbinom m n = \begin{cases}
\dfrac {m!} {n! \paren {m - n}!} & : 0 \le n \le m \\
& \\
0 & : \text { otherwise } \end{cases}$</nowiki>
Thus when $n > 1$:
:$\dbinom 1 n = 0$
and when $n < 0$:
:$\dbinom 1 n = 0$
Then:
{{begin-eqn}}
{{eqn | l = \dbinom 1 0
      | r = \dfrac {1!} {0! \paren {0 - 1}!}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = 1
      | c = {{Defof|Factorial}}
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \dbinom 1 1
      | r = \dbinom 1 {1 - 1}
      | c = Symmetry Rule for Binomial Coefficients
}}
{{eqn | r = \dbinom 1 0
      | c = 
}}
{{eqn | r = 1
      | c = from above
}}
{{end-eqn}}
{{qed}}
Category:Examples of Binomial Coefficients
c5vytdw3p2blzjsune082jaigl0mghz
Theorem: Separable Discrete Space is Countable

Let $T = \struct {S, \tau}$ be a discrete topological space.
Let $T$ be separable.
Then $S$ is countable.

Proof:
Let $T$ be separable.
By Space is Separable iff Density not greater than Aleph Zero:
:$\map d T \le \aleph_0$
where:
:$\map d T$ denotes the density of $T$
:$\aleph$ denotes the aleph mapping.
By definition of density:
:$\exists A \subseteq S: A$ is everywhere dense and $\map d T = \card A$
where $\card A$ denotes the cardinality of $A$.
By definition of everywhere dense set:
:$A^- = S$
where $A^-$ denotes the closure of $A$.
By Set in Discrete Topology is Clopen:
:$A$ is closed
Then by Set is Closed iff Equals Topological Closure:
:$A^- = A$
Thus by Countable iff Cardinality not greater than Aleph Zero:
:$S$ is countable.
{{qed}}
Theorem: Separable Discrete Space is Countable

Let $T = \struct {S, \tau}$ be a discrete topological space.
Let $T$ be separable.
Then $S$ is countable.

Proof:
Let $T$ be separable.
{{AimForCont}} $S$ is uncountable.
Then by Uncountable Discrete Space is not Separable, $T$ is not separable.
Hence the result by Proof by Contradiction.
{{qed}}
Theorem: Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk/Proof 1/Basis for the Induction

Let $r, s, t \in \R, n \in \Z$.
Consider the equation:
:$\ds (1): \quad \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$
where $\dbinom {r - t k} k$ etc. are binomial coefficients.
Then equation $(1)$ holds for the special case where $s = n - 1 - r + n t$.

Proof:
Substituting $n - 1 - r + n t$ for $s$ in the {{RHS}}:
{{begin-eqn}}
{{eqn | l = \binom {r + s - t n} n
      | r = \binom {r + \paren {n - 1 - r + n t} - t n} n
      | c = 
}}
{{eqn | r = \binom {r + n - 1 - r + n t - t n} n
      | c = 
}}
{{eqn | r = \binom {n - 1} n
      | c = 
}}
{{end-eqn}}
Substituting $n - 1 - r + n t$ for $s$ in the {{LHS}}:
{{begin-eqn}}
{{eqn | o =
      | r = \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - 1 - r + t k} {n - k} \frac r {r - t k}
      | c = 
}}
{{eqn | r = \sum_{k \mathop \ge 0} \dfrac {\paren {r - t k}! \paren {n - 1 - r + t k}! \, r} {k! \paren {r - t k - k}! \paren {n - k}! \paren {k - 1 - r + t k}! \paren {r - t k} }
      | c = 
}}
{{eqn | r = \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \dfrac {\paren {r - t k - 1}! \paren {n - 1 - r + t k}!} {\paren {r - t k - k}! \paren {k - 1 - r + t k}!}
      | c = 
}}
{{eqn | r = \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \prod_{0 \mathop < j \mathop < k} \paren {r - t k - j} \prod_{0 \mathop < j \mathop < n \mathop - k} \paren {n - 1 - r + t k - j}
      | c = 
}}
{{eqn | r = \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \paren {-1}^{k - 1} \prod_{0 \mathop < j \mathop < k} \paren {-r + t k + j} \prod_{k \mathop \le j \mathop < n} \paren {- r + t k + j}
      | c = 
}}
{{end-eqn}}
The two products give a polynomial of degree $n - 1$ in $k$.
Hence the sum for all $k$ is $0$.
Thus we have:
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - 1 - r + t k} {n - k} \frac r {r - t k}
      | r = 0
      | c = 
}}
{{eqn | r = \binom {n - 1} n
      | c = {{Defof|Binomial Coefficient}}
}}
{{end-eqn}}
Thus the equation indeed holds for the special case where $s = n - 1 - r + n t$.
Theorem: Continuous iff Meet-Continuous and There Exists Smallest Auxiliary Approximating Relation

Let $L = \struct {S, \vee, \wedge, \preceq}$ be a complete lattice.
Then:
:$L$ is continuous
{{iff}}:
:$L$ is meet-continuous and there exists the smallest auxiliary approximating relation on $S$
That is:
:$L$ is continuous
{{iff}}:
:$L$ is meet-continuous and there exists an auxiliary approximating relation $\RR$ on $S$
::for every auxiliary approximating relation $\QQ$ on $S$: $\RR \subseteq \QQ$

Proof:
=== Sufficient Condition ===
Let $L$ be continuous.
Thus by Continuous Lattice is Meet-Continuous:
:$L$ is meet-continuous.
Thus by Way Below is Approximating Relation and Way Below Relation is Auxiliary Relation:
:$\ll$ is auxiliary approximating relation on $S$.
Thus by Continuous Lattice iff Auxiliary Approximating Relation is Superset of Way Below Relation:
:for every auxiliary approximating relation $\QQ$ on $S$: $\ll \subseteq \QQ$
{{qed|lemma}}
Theorem: Continuous Lattice iff Auxiliary Approximating Relation is Superset of Way Below Relation

Let $L = \struct {S, \vee, \wedge, \preceq}$ be a complete lattice.
Let $\map {\operatorname{App} } L$ be the set of all auxiliary approximating relation on $S$.
Then
:$L$ is continuous
{{iff}}
:$\forall \RR \in \map {\operatorname{App} } L: \ll \subseteq \RR$ and $\ll$ is an approximating relation

Proof:
=== Sufficient Condition ===
Let $L$ be continuous.
Let $\RR \in \map {\operatorname{App} } L$
Let $\tuple {a, b} \in S \times S$ such that:
:$a \ll b$
By definition of way below closure:
:$a \in b^\ll$
where $b^\ll$ denotes the way below closure of $b$.
By Complete Lattice is Bounded and Continuous Lattice is Meet-Continuous:
$L$ is a bounded below meet-continuous lattice.
By Intersection of Relation Segments of Approximating Relations equals Way Below Closure:
:$\ds \bigcap \set {b^\RR: \RR \in \map {\operatorname{App} } L} = b^\ll$
where $b^\RR$ denotes the $\RR$-segment of $b$.
By Intersection is Subset/General Result:
:$b^\ll \subseteq b^\RR$
By definition of subset:
:$a \in b^\RR$
By definition of $\RR$-segment:
:$\tuple {a, b} \in \RR$
Thus by definition of subset:
:$\ll \subseteq \RR$
Thus by Way Below is Approximating Relation:
:$\ll$ is an approximating relation.
{{qed|lemma}}
Theorem: Completely Additive Function is Additive

Let $f: \N \to \C$ be a completely additive function.
Then $f$ is also additive.

Proof:
Let $m, n$ be coprime integers.
Then in particular, $m, n \in \Z$.
Hence, since $f$ is completely additive:
:$f \left({m \times n}\right) = f \left({m}\right) + f \left({n}\right)$
and $f$ is additive, as desired.
{{qed}}
Category:Number Theory
Category:Ring Theory
okn9cbt94w16hdr1f8wcq1ox7gqmhnb