avewright/proofwiki-math huggingface dataset:
Theorem: Subtraction on Numbers is Not Associative

The operation of subtraction on the numbers is not associative.
That is, in general:
:$a - \paren {b - c} \ne \paren {a - b} - c$

Proof:
By definition of subtraction:
{{begin-eqn}}
{{eqn | l = a - \paren {b - c}
      | r = a + \paren {-\paren {b + \paren {-c} } }
      | c = 
}}
{{eqn | r = a + \paren {-b} + c
      | c = 
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = \paren {a - b} - c
      | r = \paren {a + \paren {-b} } + \paren {-c}
      | c = 
}}
{{eqn | r = a + \paren {-b} + \paren {-c}
      | c = 
}}
{{end-eqn}}
So we see that:
:$a - \paren {b - c} = \paren {a - b} - c \iff c = 0$
and so in general:
:$a - \paren {b - c} \ne \paren {a - b} - c$
{{qed}}
Theorem: Identity Element of Multiplication on Numbers

On all the number systems:
* natural numbers $\N$
* integers $\Z$
* rational numbers $\Q$
* real numbers $\R$
* complex numbers $\C$
the identity element of multiplication is one ($1$).

Proof:
This is demonstrated in these pages:
* Identity Element of Natural Number Multiplication is One
* Integer Multiplication Identity is One
* Rational Multiplication Identity is One
* Real Multiplication Identity is One
* Complex Multiplication Identity is One
{{qed}}
Theorem: Identity Element of Addition on Numbers

On all the number systems:
* natural numbers $\N$
* integers $\Z$
* rational numbers $\Q$
* real numbers $\R$
* complex numbers $\C$
the identity element of addition is zero ($0$).

Proof:
This is demonstrated in these pages:
* Identity Element of Natural Number Addition is Zero
* Integer Addition Identity is Zero
* Rational Addition Identity is Zero
* Real Addition Identity is Zero
* Complex Addition Identity is Zero
{{qed}}
Theorem: Zero Element is Unique

Let $\struct {S, \circ}$ be an algebraic structure that has a zero element $z \in S$.
Then $z$ is unique.

Proof:
Suppose $z_1$ and $z_2$ are both zeroes of $\struct {S, \circ}$.
Then by the definition of zero element:
:$z_2 \circ z_1 = z_1$ by dint of $z_1$ being a zero
:$z_2 \circ z_1 = z_2$ by dint of $z_2$ being a zero.
So $z_1 = z_2 \circ z_1 = z_2$.
So $z_1 = z_2$ and there is only one zero after all.
{{qed}}
Theorem: Group with Zero Element is Trivial

Let $\struct {G, \circ}$ be a group.
Let $\struct {G, \circ}$ have a zero element.
Then $\struct {G, \circ}$ is the trivial group.

Proof:
Let $e \in G$ be the identity element of $G$.
Let $z \in G$ be a zero element.
Let $x \in G$ be any arbitrary element of $\struct {G, \circ}$.
Then:
{{begin-eqn}}
{{eqn | l = x
      | r = x \circ e
      | c = {{Group-axiom|2}}
}}
{{eqn | r = x \circ \paren {z \circ z^{-1} }
      | c = {{Group-axiom|3}}
}}
{{eqn | r = \paren {x \circ z} \circ z^{-1}
      | c = {{Group-axiom|1}}
}}
{{eqn | r = z \circ z^{-1}
      | c = {{Defof|Zero Element}}: $x \circ z = z$
}}
{{eqn | r = e
      | c = {{Group-axiom|3}}
}}
{{end-eqn}}
So whatever $x \in G$ is, it has to be the identity element of $G$.
So $G$ can contain only that one element, and is therefore the trivial group.
{{qed}}
Theorem: Count of Binary Operations on Set

Let $S$ be a set whose cardinality is $n$.
The number $N$ of different binary operations that can be applied to $S$ is given by:
:$N = n^{\paren {n^2} }$

Proof:
A binary operation on $S$ is by definition a mapping from the cartesian product $S \times S$ to the set $S$.
Thus we are looking to evaluate:
:$N = \card {\set {f: S \times S \to S} }$ 
The domain of $f$ has $n^2$ elements, from Cardinality of Cartesian Product of Finite Sets of Finite Sets.
The result follows from Cardinality of Set of All Mappings.
{{qed}}
Theorem: Count of Commutative Binary Operations on Set

Let $S$ be a set whose cardinality is $n$.
The number $N$ of possible different commutative binary operations that can be applied to $S$ is given by:
:$N = n^{\frac {n \paren {n + 1} } 2}$

Proof:
Let $\struct {S, \circ}$ be a magma.
From Cardinality of Cartesian Product of Finite Sets, there are $n^2$ elements in $S \times S$.
The binary operations $\circ$ is commutative {{iff}}:
:$\forall x, y \in S: x \circ y = y \circ x$
Thus for every pair of elements $\tuple {x, y} \in S \times S$, it is required that $\tuple {y, x} \in S \times S$.
So the question boils down to establishing how many different ''unordered'' pairs there are in $S$.
That is, how many doubleton subsets there are in $S$.
From Cardinality of Set of Subsets, this is given by:
:$\dbinom n 2 = \dfrac {n \paren {n - 1} } 2$
To that set of doubleton subsets, we also need to add those ordered pairs where $x = y$.
There are clearly $n$ of these.
So the total number of pairs in question is:
:$\dfrac {n \paren {n - 1} } 2 + n = \dfrac {n \paren {n + 1} } 2$
The result follows from Cardinality of Set of All Mappings.
{{qed}}
Theorem: Count of Binary Operations with Fixed Identity

Let $S$ be a set whose cardinality is $n$.
Let $x \in S$.
The number $N$ of possible different binary operations such that $x$ is an identity element that can be applied to $S$ is given by:
:$N = n^{\paren {\paren {n - 1}^2} }$

Proof:
Let $S$ be a set such that $\card S = n$.
Let $x \in S$ be an identity element.
From Count of Binary Operations on Set, there are $n^{\paren {n^2} }$ binary operations in total.
We also know that $a \in S \implies a \circ x = a = x \circ a$, so all operations on $x$ are already specified.
It remains to count all possible combinations of the remaining $n - 1$ elements.
This is effectively counting the mappings $\paren {S \setminus \set x} \times \paren {S \setminus \set x} \to S$.
From Count of Binary Operations on Set, this is $n^{\paren {\paren {n - 1}^2} }$ structures with $x$ as the identity element.
{{qed}}
Theorem: Count of Commutative Binary Operations with Fixed Identity

Let $S$ be a set whose cardinality is $n$.
Let $x \in S$.
The number $N$ of possible different commutative binary operations such that $x$ is an identity element that can be applied to $S$ is given by:
:$N = n^{\frac {n \paren {n - 1} } 2}$

Proof:
This follows by the arguments of Count of Binary Operations with Fixed Identity and Count of Commutative Binary Operations on Set.
From Count of Binary Operations on Set, there are $n^{\paren {n^2} }$ binary operations in total.
We also know that:
:$a \in S \implies a \circ x = a = x \circ a$
so all binary operations on $x$ are already specified.
It remains to count all possible combinations of the remaining $n-1$ elements.
This is effectively counting the mappings:
:$\paren {S \setminus \set x} \times \paren {S \setminus \set x} \to S$
So the question boils down to establishing how many different ''unordered'' pairs there are in $\paren {S \setminus \set x}$.
That is, how many doubleton subsets there are in $\paren {S \setminus \set x}$.
From Cardinality of Set of Subsets, this is given by:
:$\dbinom {n - 1} 2 = \dfrac {\paren {n - 1} \paren {n - 2} } 2$
To that set of doubleton subsets, we also need to add those ordered pairs where $x = y$.
There are clearly $n - 1$ of these.
So the total number of pairs in question is:
:$\dfrac {\paren {n - 1} \paren {n - 2} } 2 + n - 1 = \dfrac {n \paren {n - 1} } 2$
The result follows from Cardinality of Set of All Mappings.
{{qed}}
Theorem: Count of Binary Operations with Identity

Let $S$ be a set whose cardinality is $n$.
The number $N$ of possible different binary operations which have an identity element that can be applied to $S$ is given by:
:$N = n^{\paren {n - 1}^2 + 1}$

Proof:
From Count of Binary Operations with Fixed Identity, there are $n^{\paren {n - 1}^2}$ such binary operations for each individual element of $S$.
As Identity is Unique, if $x$ is the identity, no other element can also be an identity.
As there are $n$ different ways of choosing such an identity, there are $n \times n^{\paren {n - 1}^2}$ different magmas with an identity.
These are guaranteed not to overlap by the uniqueness of the identity.
Hence the result.
{{qed}}
Theorem: Count of Commutative Binary Operations with Identity

Let $S$ be a set whose cardinality is $n$.
The number $N$ of possible different commutative binary operations that can be applied to $S$ which have an identity element is given by:
:$N = n^{\frac {n \paren {n - 1} } 2 + 1}$

Proof:
From Count of Commutative Binary Operations with Fixed Identity, there are $n^{\frac {n \paren {n - 1} } 2}$ such binary operations for each individual element of $S$.
As Identity is Unique, if $x$ is the identity, no other element can also be an identity.
As there are $n$ different ways of choosing such an identity, there are $n \times n^{\frac {n \paren {n - 1} } 2}$ different algebraic structures with an identity.
These are guaranteed not to overlap by the uniqueness of the identity.
Hence the result.
{{qed}}
Theorem: Count of Binary Operations Without Identity

Let $S$ be a set whose cardinality is $n$.
The number $N$ of possible different binary operations which do not have an identity element that can be applied to $S$ is given by:
:$N = n^{\paren {\paren {n - 1}^2 + 1} } \paren {n^{2 \paren {n - 1} } - 1}$

Proof:
From Count of Binary Operations on Set, the total number of operations is $n^{\paren {n^2} }$.
From Count of Binary Operations with Identity, the total number of operations with an identity is $n^{\paren {n - 1}^2 + 1}$.
So the total number of operations without an identity is:
:$n^{\paren {n^2} } - n^{\paren {n - 1}^2 + 1} = n^{\paren {\paren {n - 1}^2 + 1} } \paren {n^{2 \paren {n - 1} } - 1}$
Hence the result.
{{qed}}
Theorem: Power of Element in Subgroup

Let $\struct {G, \circ}$ be a group whose identity is $e$.
Let $\struct {H, \circ}$ be a subgroup of $\struct {G, \circ}$.
Let $x \in H$.
Then:
:$\forall n \in \Z: x^n \in H$

Proof:
Proof by induction:
For all $n \in \N^*$, let $\map P n$ be the compound proposition:
:$x^n \in H \text{ and } x^{-n} \in H$.
$\map P 0$ is true, as this just says $x^0 \in H$.
By Powers of Group Elements, $x^0 = e$.
This follows by Identity of Subgroup.
Theorem: Element to Power of Remainder

:$\forall n \in \Z: n = q k + r: 0 \le r < k \iff a^n = a^r$

Proof:
Let $n \in \Z$.
We have:
{{begin-eqn}}
{{eqn | l = n
      | r = q k + r
      | c = 
}}
{{eqn | ll= \leadstoandfrom
      | l = n - r
      | r = q k
      | c = 
}}
{{eqn | ll= \leadstoandfrom
      | l = k
      | o = \divides
      | r = \paren {n - r}
      | c = 
}}
{{end-eqn}}
The result follows from Equal Powers of Finite Order Element.
{{qed}}
Theorem: Element to Power of Multiple of Order is Identity

:$\forall n \in \Z: k \divides n \iff a^n = e$

Proof:
Let $k \in \N$ be the smallest such that $a^k = e$ as per the hypothesis.
Theorem: List of Elements in Finite Cyclic Group

:$\set {a^0, a^1, a^2, \ldots, a^{k - 1} }$ is a complete repetition-free list of the elements of $\gen a$

Proof:
By Element to Power of Remainder, every power of $a$ is equal to one appearing in the list $a^0, a^1, a^2, \ldots, a^{k - 1}$.
This list has to be repetition free, otherwise it would contain $a^m = a^n$ with $0 \le m < n < k$ which contradicts the hypothesis.
{{qed}}
Theorem: Equivalence of Definitions of Order of Group Element

{{TFAE|def = Order of Group Element}}
Let $G$ be a group whose identity is $e$.
Let $x \in G$.

Proof:
Let $k$ be the order of $x$ in $G$ according to Definition 1.
Let $l$ be the order of $x$ in $G$ according to Definition 3.
Theorem: Rising Sum of Binomial Coefficients

:$\ds \sum_{j \mathop = 0}^m \binom {n + j} n = \binom {n + m + 1} {n + 1} = \binom {n + m + 1} m$

Proof:
Proof by induction:
Let $n \in \Z$.
For all $m \in \N$, let $\map P m$ be the proposition:
:$\ds \sum_{j \mathop = 0}^m \binom {n + j} n = \binom {n + m + 1} {n + 1}$
$\map P 0$ is true, as this just says:
:$\dbinom n n = \dbinom {n + 1} {n + 1}$
But $\dbinom n n = \dbinom {n + 1} {n + 1} = 1$ from the {{Defof|Binomial Coefficient}}.
=== Basis for the Induction ===
$\map P 1$ is the case:
{{begin-eqn}}
{{eqn | l = \sum_{j \mathop = 0}^1 \binom {n + j} n
      | r = \binom n n + \binom {n + 1} n
      | c = 
}}
{{eqn | r = 1 + \paren {n + 1}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = n + 2
      | c = 
}}
{{eqn | r = \binom {n + 2} {n + 1}
      | c = {{Defof|Binomial Coefficient}}
}}
{{end-eqn}}
So:
:$\ds \sum_{j \mathop = 0}^1 \binom {n + j} n = \binom {n + 2} {n + 1}$
and $\map P 1$ is seen to hold.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\ds \sum_{j \mathop = 0}^k \binom {n + j} n = \binom {n + k + 1} {n + 1}$
Then we need to show:
:$\ds \sum_{j \mathop = 0}^{k+1} \binom {n + j} n = \binom {n + k + 2} {n + 1}$
=== Induction Step ===
This is our induction step:
{{begin-eqn}}
{{eqn | l = \sum_{j \mathop = 0}^{k + 1} \binom {n + j} n
      | r = \sum_{j \mathop = 0}^k \binom {n + j} n + \binom {n + k + 1} n
      | c = 
}}
{{eqn | r = \binom {n + k + 1} {n + 1} + \binom {n + k + 1} n
      | c = Induction Hypothesis
}}
{{eqn | r = \binom {n + k + 2} {n + 1}
      | c = Pascal's Rule
}}
{{end-eqn}}
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \sum_{j \mathop = 0}^m \binom {n + j} n = \binom {n + m + 1} {n + 1}$
Finally, from Symmetry Rule for Binomial Coefficients:
:$\dbinom {n + m + 1} {n + 1} = \dbinom {n + m + 1} m$
{{qed}}
Theorem: Sum of Even Index Binomial Coefficients

:$\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1}$

Proof:
From Sum of Binomial Coefficients over Lower Index we have:
:$\ds \sum_{i \mathop \in \Z} \binom n i = 2^n$
That is:
:$\dbinom n 0 + \dbinom n 1 + \dbinom n 2 + \dbinom n 3 + \cdots + \dbinom n n = 2^n$
as $\dbinom n i = 0$ for $i < 0$ and $i > n$.
This can be written more conveniently as:
:$\dbinom n 0 + \dbinom n 1 + \dbinom n 2 + \dbinom n 3 + \dbinom n 4 + \cdots = 2^n$
Similarly, from Alternating Sum and Difference of Binomial Coefficients for Given n we have:
:$\ds \sum_{i \mathop \in \Z} \paren {-1}^i \binom n i = 0$
That is:
:$\dbinom n 0 - \dbinom n 1 + \dbinom n 2 - \dbinom n 3 + \dbinom n 4 - \cdots = 0$
Adding them together, we get:
:$2 \dbinom n 0 + 2 \dbinom n 2 + 2 \dbinom n 4 + \cdots = 2^n$
as the odd index coefficients cancel out.
Dividing by $2$ throughout gives us the result.
{{qed}}
Theorem: Sum of Even Index Binomial Coefficients

:$\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1}$

Proof:
Let ${\N_n}^*$ be the initial segment of natural numbers, one-based.
Let:
:$E_n = \set {X : \paren {X \subset {\N_n}^*} \land \paren {2 \divides \size X} }$
:$O_n = \set {X : \paren {X \subset {\N_n}^*} \land \paren {2 \nmid \size X} }$
That is:
:$E_n$ is the set of all subsets of ${\N_n}^*$ with an even number of elements
:$O_n$ is the set of all subsets of ${\N_n}^*$ with an odd number of elements.
So by Cardinality of Set of Subsets:
:$\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1} \iff \size {E_n} = 2^{n - 1}$
which is to be proved by induction below.
=== Basis of the Induction ===
Let $n = 1$.
Then
:$\size {E_n} = \size {\set \O} = 1$
and:
:$2^{n - 1} = 2^{1 - 1} = 2^0 = 1$
This is the basis for the induction.
=== Induction Hypothesis ===
This is the induction hypothesis:
:$\size {E_k} = 2^{k - 1}$
So:
:$\size {O_k} = \size {2^{ {\N_k}^*} \divides E_k} = 2^k - 2^{k - 1} = 2^{k - 1}$
=== Induction Step ===
This is the induction step:
{{begin-eqn}}
{{eqn | l = \size {E_{k + 1} }
      | r = \size {\set {X: \paren {X \subset {\N_{k + 1} }^* } \land \paren {2 \divides \size X} } }
      | c = Definition of $E_n$
}}
{{eqn | r = \size {\set {X: X \in E_k} \cup \set {X \cup \set {k + 1}: X \in O_k} }
      | c = Construction of the set with smaller sets, considering the presence of the element $k+1$
}}
{{eqn | r = \size {E_k} + \size {O_k}
      | c = $E_k$ and $O_k$ are disjoint by definition
}}
{{eqn | r = 2^{k - 1} + 2^{k - 1}
      | c = Induction Hypothesis
}}
{{eqn | r = 2^k
      | c = 
}}
{{end-eqn}}
The result follows by induction.
{{qed}}
Theorem: Sum of Odd Index Binomial Coefficients

:$\ds \sum_{i \mathop \ge 0} \binom n {2 i + 1} = 2^{n - 1}$

Proof:
From Sum of Binomial Coefficients over Lower Index we have:
:$\ds \sum_{i \mathop \in \Z} \binom n i = 2^n$
That is:
:$\dbinom n 0 + \dbinom n 1 + \dbinom n 2 + \dbinom n 3 + \cdots + \dbinom n n = 2^n$
as $\dbinom n i = 0$ for $i < 0$ and $i > n$.
This can be written more conveniently as:
:$(1): \quad \dbinom n 0 + \dbinom n 1 + \dbinom n 2 + \dbinom n 3 + \dbinom n 4 + \cdots = 2^n$
Similarly, from Alternating Sum and Difference of Binomial Coefficients for Given n we have:
:$\ds \sum_{i \mathop \in \Z} \paren {-1}^i \binom n i = 0$
That is:
:$(2): \quad \dbinom n 0 - \dbinom n 1 + \dbinom n 2 - \dbinom n 3 + \dbinom n 4 - \cdots = 0$
Subtracting $(2)$ from $(1)$, we get:
:$2 \dbinom n 1 + 2 \dbinom n 3 + 2 \dbinom n 5 + \cdots = 2^n$
as the even index coefficients cancel out.
Dividing by $2$ throughout gives us the result.
{{qed}}
Theorem: Increasing Sum of Binomial Coefficients

:$\ds \sum_{j \mathop = 0}^n j \binom n j = n 2^{n - 1}$

Proof:
{{begin-eqn}}
{{eqn | l = \sum_{j \mathop = 0}^n j \binom n j
      | r = \sum_{j \mathop = 1}^n j \binom n j
      | c = as $0 \dbinom n 0 = 0$
}}
{{eqn | r = \sum_{j \mathop = 1}^n n \binom {n - 1} {j - 1}
      | c = Factors of Binomial Coefficient
}}
{{eqn | r = n \sum_{j \mathop = 0}^{n - 1} \binom {n - 1} j
      | c = Translation of Index Variable of Summation
}}
{{eqn | r = n 2^{n - 1}
      | c = Sum of Binomial Coefficients over Lower Index
}}
{{end-eqn}}
{{qed}}
Theorem: Increasing Sum of Binomial Coefficients

:$\ds \sum_{j \mathop = 0}^n j \binom n j = n 2^{n - 1}$

Proof:
From the Binomial Theorem:
:$(1): \quad \paren {1 + x}^n = \ds \sum_{j \mathop = 0}^n \dbinom n j x^n$
Differentiating $(1)$ {{WRT|Differentiation}} $x$:
{{begin-eqn}}
{{eqn | l = n \paren {1 + x}^{n - 1}
      | r = \sum_{j \mathop = 1}^n j \dbinom n j x^{j - 1}
      | c = Power Rule for Derivatives
}}
{{eqn | ll= \leadsto
      | l = n \paren {1 + 1}^{n - 1}
      | r = \sum_{j \mathop = 1}^n j \dbinom n j
      | c = setting $x = 1$
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Increasing Sum of Binomial Coefficients

:$\ds \sum_{j \mathop = 0}^n j \binom n j = n 2^{n - 1}$

Proof:
{{begin-eqn}}
{{eqn | n = 1
      | l = \sum_{j \mathop = 0}^n j \binom n j
      | r = 0 \binom n 0 + 1 \binom n 1 + 2 \binom n 2 + 3 \binom n 3 + \cdots + \paren {n - 2} \binom n {n - 2} + \paren {n - 1} \binom n {n - 1} + n \binom n n
      | c = 
}}
{{eqn | n = 2
      | ll= \leadsto
      | l = \sum_{j \mathop = 0}^n j \binom n j
      | r = 0 \binom n n + 1 \binom n {n - 1} + 2 \binom n {n - 2} + 3 \binom n {n - 3} + \cdots + \paren {n - 2} \binom n 2 + \paren {n - 1} \binom n 1 + n \binom n 0
      | c = Symmetry Rule for Binomial Coefficients: $\dbinom n j = \dbinom n {n - j}$
}}
{{eqn | ll= \leadsto
      | l = 2 \sum_{j \mathop = 0}^n j \binom n j
      | r = n \binom n 0 + n \binom n 1 + n \binom n 2 + n \binom n 3 + \cdots + n \binom n {n - 2} + n \binom n {n - 1} + n \binom n n
      | c = adding $(1)$ to $(2)$
}}
{{eqn | r = n \paren {\binom n 0 + \binom n 1 + \binom n 2 + \binom n 3 + \cdots + \binom n {n - 2} + \binom n {n - 1} + \binom n n}
      | c = 
}}
{{eqn | r = n \sum_{j \mathop = 0}^n \binom n j
      | c = 
}}
{{eqn | r = n 2^n
      | c = Sum of Binomial Coefficients over Lower Index
}}
{{eqn | ll= \leadsto
      | l = \sum_{r \mathop = 1}^n j \binom n j
      | r = n 2^{n - 1}
      | c = dividing both sides by $2$
}}
{{end-eqn}}
{{qed}}
Theorem: Increasing Alternating Sum of Binomial Coefficients

:$\ds \sum_{j \mathop = 0}^n \paren {-1}^{n + 1} j \binom n j = 0$

Proof:
{{begin-eqn}}
{{eqn | l = \sum_{j \mathop = 0}^n \paren {-1}^{n + 1} j \binom n j
      | r = \sum_{j \mathop = 1}^n \paren {-1}^{n + 1} j \binom n j
      | c = as $0 \dbinom n 0 = 0$
}}
{{eqn | r = \sum_{j \mathop = 1}^n \paren {-1}^{n + 1} n \binom {n - 1} {j - 1}
      | c = Factors of Binomial Coefficient
}}
{{eqn | r = n \sum_{j \mathop = 0}^{n - 1} \paren {-1}^{n - 1} \binom {n - 1} j
      | c = Translation of Index Variable of Summation, and $\paren {-1}^{n + 1} = \paren {-1}^{n - 1}$
}}
{{eqn | r = 0
      | c = Alternating Sum and Difference of Binomial Coefficients for Given n
}}
{{end-eqn}}
{{qed}}
Theorem: Sum of Squares of Binomial Coefficients

{{begin-eqn}}
{{eqn | l = \sum_{i \mathop = 0}^n \binom n i^2
      | r = \binom {2 n} n
}}
{{eqn | r = \dfrac {\paren {2 n}!} {\paren {n!}^2}
}}
{{end-eqn}}

Proof:
Consider the Binomial Theorem:
{{begin-eqn}}
{{eqn | q = \forall n \in \Z_{\ge 0}
      | l = \paren {1 + x}^n
      | r = \sum_{j \mathop = 0}^n \dbinom n j x^j
      | c = 
}}
{{eqn | r = \dbinom n 0 x^0 + \dbinom n 1 x^1 + \dbinom n 2 x^2 + \cdots + \dbinom n {n - 1} x^{n - 1} + \dbinom n n x^n
      | c = 
}}
{{eqn | n = 1
      | r = \dbinom n n x^0 + \dbinom n {n - 1} x^1 + \dbinom n {n - 2} x^2 + \cdots + \dbinom n 1 x^{n - 1} + \dbinom n 0 x^n
      | c = Symmetry Rule for Binomial Coefficients
}}
{{end-eqn}}
Let $m$ be the coefficient of $x^n$ in the expansion of $\paren {1 + x}^{2 n} = \paren {1 + x}^n \times \paren {1 + x}^n$.
For all $k \in \set {0, 1, \ldots, n}$, by matching up the coefficient of $x^k$ with that of $x^{n - k}$ in $(1)$, we have:
:$m = \ds \sum_{k \mathop = 0}^n \dbinom n k^2$
But from the Binomial Theorem, this given by:
:$m = \dbinom {2 n} n$
Hence the result.
Theorem: Sum of Squares of Binomial Coefficients

{{begin-eqn}}
{{eqn | l = \sum_{i \mathop = 0}^n \binom n i^2
      | r = \binom {2 n} n
}}
{{eqn | r = \dfrac {\paren {2 n}!} {\paren {n!}^2}
}}
{{end-eqn}}

Proof:
Consider the number of paths in the integer lattice from $\tuple {0, 0}$ to $\tuple {n, n}$ using only single steps of the form:
:$\tuple {i, j} \to \tuple {i + 1, j}$
:$\tuple {i, j} \to \tuple {i, j + 1}$
that is, either to the right or up.
This process takes $2 n$ steps, of which $n$ are steps to the right.
Thus the total number of paths through the graph is equal to $\dbinom {2 n} n$.
Now let us count the paths through the grid by first counting the paths:
:$(1): \quad$ from $\tuple {0, 0}$ to $\tuple {k, n - k}$
and then the paths:
:$(2): \quad$ from $\tuple {k, n - k}$ to $\tuple {n, n}$.
Note that each of these paths is of length $n$.
Since each path is $n$ steps long, every endpoint will be of the form $\tuple {k, n - k}$ for some $k \in \set {1, 2, \ldots, n}$, representing $k$ steps right and $n-k$ steps up.
Note that the number of paths through $\tuple {k, n - k}$ is equal to $\dbinom n k$, since we are free to choose the $k$ steps right in any order.
We can also count the number of $n$-step paths from the point $\tuple {k, n - k}$ to $\tuple {n, n}$.
These paths will be composed of $n - k$ steps to the right and $k$ steps up.
Therefore the number of these paths is equal to $\dbinom n {n - k} = \dbinom n k$.
Thus the total number of paths from $\tuple {0, 0}$ to $\tuple {n, n}$ that pass through $\tuple {k, n - k}$ is equal to the product of:
:the number of possible paths from $\tuple {0, 0}$ to $\tuple {k, n - k}$, which equals $\dbinom n k$
and:
:the number of possible paths from $\tuple {k, n - k}$ to $\tuple {n, n}$, which equals $\dbinom n k$.
So the total number of paths through $\tuple {k, n - k}$ is equal to $\dbinom n k^2$.
Summing over all possible values of $k \in 0, \ldots, n$ gives the total number of paths.
Thus we get:
:$\ds \sum_{k \mathop = 0}^n \binom n k^2 = \binom {2 n} n$
{{qed}}