avewright/proofwiki-math huggingface dataset:
Theorem: Inverse of Combinatorial Matrix

Let $C_n$ be the combinatorial matrix of order $n$ given by:
:$C_n = \begin{bmatrix}
x + y & y & \cdots & y \\
y & x + y & \cdots & y \\
\vdots & \vdots & \ddots & \vdots \\
y & y & \cdots & x + y
\end{bmatrix}$
Then its inverse $C_n^{-1} = \sqbrk b_n$ can be specified as:
:$b_{i j} = \dfrac {-y + \delta_{i j} \paren {x + n y} } {x \paren {x + n y} }$
where $\delta_{i j}$ is the Kronecker delta.

Proof:
From the definition of the combinatorial matrix:
:$C_n = x \mathbf I_n + y \mathbf J_n$
where:
:$\mathbf I_n$ is the unit matrix of order $n$
:$\mathbf J_n$ is the square ones matrix of order $n$.
From Square of Ones Matrix we have $\mathbf J_n^2 = n \mathbf J_n$.
Hence:
{{begin-eqn}}
{{eqn | l = \paren {x \mathbf I_n + y \mathbf J_n} \paren {x \mathbf I_n - y \mathbf J_n}
      | r = x^2 \mathbf I_n - n y^2 \mathbf J_n
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {x \mathbf I_n + y \mathbf J_n} \paren {x \mathbf I_n - y \mathbf J_n} + n y^2 \mathbf J_n
      | r = x^2 \mathbf I_n
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {x \mathbf I_n + y \mathbf J_n} \paren {x \mathbf I_n - y \mathbf J_n} + n y \mathbf I_n y \mathbf J_n
      | r = x^2 \mathbf I_n
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {x \mathbf I_n + y \mathbf J_n} \paren {x \mathbf I_n - y \mathbf J_n} + x n y \mathbf I_n + n y \mathbf I_n y \mathbf J_n
      | r = x^2 \mathbf I_n + x n y \mathbf I_n
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {x \mathbf I_n + y \mathbf J_n} \paren {x \mathbf I_n - y \mathbf J_n} + n y \mathbf I_n \paren {x \mathbf I_n + y \mathbf J_n}
      | r = x^2 \mathbf I_n + x n y \mathbf I_n
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {x \mathbf I_n + y \mathbf J_n} \paren {\paren {x + n y} \mathbf I_n - y \mathbf J_n}
      | r = x \paren {x + n y} \mathbf I_n
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {x \mathbf I_n + y \mathbf J_n} \paren {\frac {\paren {x + n y} } {x \paren {x + n y} } \mathbf I_n - \frac y {x \paren {x + n y} } \mathbf J_n}
      | r = \mathbf I_n
      | c = 
}}
{{end-eqn}}
So we have found a specification for the matrix which, when multiplied by $C_n$, yields $\mathbf I_n$.
By using the identities $\mathbf I_n = \sqbrk {\delta_{i j} }_n$ and $\mathbf J_n = \sqbrk 1_n$ we obtain the stated result:
:$b_{i j} = \dfrac {-y + \delta_{i j} \paren {x + n y} } {x \paren {x + n y} }$
{{qed}}
Theorem: Floor Function is Idempotent

:$\floor {\floor x} = \floor x$

Proof:
Let $y = \floor x$.
By Floor Function is Integer, $y$ is an integer.
Then from Real Number is Integer iff equals Floor:
:$\floor y = y$
So:
:$\floor {\floor x} = \floor x$
{{qed}}
Theorem: Kronecker's Lemma

Let $\sequence {x_n}$ be an infinite sequence of real numbers such that:
:$\ds \sum_{n \mathop = 1}^\infty x_n = s$ 
exists and is finite.
Then for $0 < b_1 \le b_2 \le b_3 \le \ldots$ and $b_n \to \infty$: 
:$\ds \lim_{n \mathop \to \infty} \frac 1 {b_n} \sum_{k \mathop = 1}^n b_k x_k = 0$

Proof:
Let $S_k$ denote the partial sums of the $x$s.
Using Summation by Parts:
:$\ds \frac 1 {b_n} \sum_{k \mathop = 1}^n b_k x_k = S_n - \frac 1 {b_n} \sum_{k \mathop = 1}^{n - 1} \paren {b_{k + 1} - b_k} S_k$
Now, pick any $\epsilon \in \R_{>0}$.
Choose $N$ such that $S_k$ is $\epsilon$-close to $s$ for $k > N$.
This can be done, as the sequence $S_k$ converges to $s$.
Then the {{RHS}} is:
{{begin-eqn}}
{{eqn | o =
      | r = S_n - \frac 1 {b_n} \sum_{k \mathop = 1}^{N - 1} \paren {b_{k + 1} - b_k} S_k - \frac 1 {b_n} \sum_{k \mathop = N}^{n - 1} \paren {b_{k + 1} - b_k} S_k
      | c = 
}}
{{eqn | r = S_n - \frac 1 {b_n} \sum_{k \mathop = 1}^{N - 1} \paren {b_{k + 1} - b_k} S_k - \frac 1 {b_n} \sum_{k \mathop = N}^{n - 1} \paren {b_{k + 1} - b_k} s - \frac 1 {b_n} \sum_{k \mathop = N}^{n - 1} \paren {b_{k + 1} - b_k} \paren {S_k - s}
      | c = 
}}
{{eqn | r = S_n - \frac 1 {b_n} \sum_{k \mathop = 1}^{N - 1} \paren {b_{k + 1} - b_k} S_k - \frac {b_n - b_N} {b_n} s - \frac 1 {b_n} \sum_{k \mathop = N}^{n - 1} \paren {b_{k + 1} - b_k} \paren {S_k - s}
      | c = 
}}
{{end-eqn}}
Now, let $n \to \infty$.
The first term goes to $s$, which cancels with the third term.
The second term goes to zero (as the sum is a fixed value).
Since the $b$ sequence is increasing, the last term is bounded by $\epsilon \dfrac {b_n - b_N} {b_n} \le \epsilon$.
{{qed}}
{{MissingLinks|Needs tightening up a bit, linking to existing results, some definitions need doing.}}
{{Namedfor|Leopold Kronecker|cat = Kronecker}}
Theorem: Number of Permutations

Let $S$ be a set of $n$ elements.
Let $r \in \N: r \le n$.
The number of $r$-permutations of $S$ is:
:${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
Using the falling factorial symbol, this can also be expressed:
:${}^n P_r = n^{\underline r}$

Proof:
We are seeking to calculate the number of $r$-permutations of $S$, that is ${}^n P_r$, where $r = n$.
Hence:
{{begin-eqn}}
{{eqn | l = {}^n P_n
      | r = \dfrac {n!} {\paren {n - n}!}
      | c = Number of Permutations
}}
{{eqn | r = n!
      | c = {{Defof|Factorial}}
}}
{{end-eqn}}
{{qed}}
Theorem: Number of Permutations

Let $S$ be a set of $n$ elements.
Let $r \in \N: r \le n$.
The number of $r$-permutations of $S$ is:
:${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
Using the falling factorial symbol, this can also be expressed:
:${}^n P_r = n^{\underline r}$

Proof:
We pick the elements of $S$ in an arbitrary order.
There are $n$ elements of $S$, so there are $n$ options for the first element.
Then there are $n - 1$ elements left in $S$ that we have not picked, so there are $n - 1$ options for the second element.
Then there are $n - 2$ elements left, so there are $n - 2$ options for the third element.
And so on, until there are $3$, then $2$, then $1$ remaining elements.
Each mapping is independent of the choices made for all the other mappings.
So, by the Product Rule for Counting, the total number of ordered selections from $S$:
{{begin-eqn}}
{{eqn | l = {}^n P_n
      | r = n \paren {n - 1} \paren {n - 2} \cdots 3 \times 2 \times 1
}}
{{eqn | r = n!
      | c = {{Defof|Factorial}}
}}
{{end-eqn}}
{{qed}}
Theorem: Number of Permutations

Let $S$ be a set of $n$ elements.
Let $r \in \N: r \le n$.
The number of $r$-permutations of $S$ is:
:${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
Using the falling factorial symbol, this can also be expressed:
:${}^n P_r = n^{\underline r}$

Proof:
From the definition, it can be seen that a bijection $f: S \to S$ is an $n$-permutation.
Hence, from Cardinality of Set of Bijections the number of $n$-permutations on a set of $n$ elements is:
:${}^n P_n = \dfrac {n!} {\paren {n - n}!} = n!$
{{qed}}
Theorem: Number of Permutations

Let $S$ be a set of $n$ elements.
Let $r \in \N: r \le n$.
The number of $r$-permutations of $S$ is:
:${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
Using the falling factorial symbol, this can also be expressed:
:${}^n P_r = n^{\underline r}$

Proof:
{{begin-eqn}}
{{eqn | l = {}^{n - 1} P_n
      | r = \dfrac {n!} {\paren {n - \paren {n - 1} }!}
      | c = Number of Permutations
}}
{{eqn | r = \dfrac {n!} {1!}
      | c = 
}}
{{eqn | r = n!
      | c = 
}}
{{eqn | r = {}^n P_n
      | c = Number of Permutations
}}
{{end-eqn}}
{{qed}}
Theorem: Number of Permutations

Let $S$ be a set of $n$ elements.
Let $r \in \N: r \le n$.
The number of $r$-permutations of $S$ is:
:${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
Using the falling factorial symbol, this can also be expressed:
:${}^n P_r = n^{\underline r}$

Proof:
{{begin-eqn}}
{{eqn | l = {}^{n - 1} P_n
      | r = n^{\underline {n - 1} }
      | c = Number of Permutations: $n^{\underline {n - 1} }$ denotes Falling Factorial
}}
{{eqn | r = n!
      | c = Integer to Power of Itself Less One Falling is Factorial
}}
{{eqn | r = {}^n P_n
      | c = Number of Permutations
}}
{{end-eqn}}
{{qed}}
Theorem: Number of Permutations

Let $S$ be a set of $n$ elements.
Let $r \in \N: r \le n$.
The number of $r$-permutations of $S$ is:
:${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
Using the falling factorial symbol, this can also be expressed:
:${}^n P_r = n^{\underline r}$

Proof:
We pick the elements of $S$ in any arbitrary order.
There are $n$ elements of $S$, so there are $n$ options for the first element.
Then there are $n - 1$ elements left in $S$ that we haven't picked, so there are $n-1$ options for the second element.
Then there are $n - 2$ elements left, so there are $n - 2$ options for the third element.
And so on, to the $r$th element of our selection: we now have $n - \paren {r - 1}$ possible choices.
Each mapping is independent of the choices made for all the other mappings, so by the Product Rule for Counting, the total number of ordered selections from $S$:
{{begin-eqn}}
{{eqn | l = {}^n P_r
      | r = n \paren {n - 1} \paren {n - 2} \cdots \paren {n - r + 1}
}}
{{eqn | r = n \paren {n - 1} \paren {n - 2} \ldots \paren {n - r + 1} \dfrac {\paren {n - r}!} {\paren {n - r}!} 
      | c = multiplying top and bottom by $\paren {n - r}!$
}}
{{eqn | r = \dfrac {n!} {\paren {n - r}!}
      | c = simplifying the numerator
}}
{{end-eqn}}
{{qed}}
Theorem: Number of Permutations

Let $S$ be a set of $n$ elements.
Let $r \in \N: r \le n$.
The number of $r$-permutations of $S$ is:
:${}^n P_r = \dfrac {n!} {\paren {n - r}!}$
Using the falling factorial symbol, this can also be expressed:
:${}^n P_r = n^{\underline r}$

Proof:
By definition, an $r$-permutation of $S$ is an ordered selection of $r$ elements of $S$.
Also, an $r$-permutation of $S$ is {{afortiori}} an injection from a subset of $S$ into $S$.
The result is immediate from Cardinality of Set of Injections.
{{qed}}
Theorem: Construction of Permutations

The ${}^n P_n$ permutations of $n$ objects can be generated algorithmically.
By Number of Permutations, that number is given by:
:${}^n P_n = n!$
where $n!$ denotes the factorial of $n$.
This will be demonstrated to hold.

Proof:
The following is an inductive method of creating all the permutations of $n$ objects.
=== Base Case ===
There is clearly one way to arrange one object in order.
=== Inductive Hypothesis ===
We assume that we have constructed all $n!$ permutations of $n$ objects.
=== Induction Step ===
{{WLOG}}, let a set $S_n$ of $n$ objects be $\set {1, 2, \ldots, n}$.
Take a permutation of $S_n$:
:$a_1 \, a_2 \, a_3 \, \ldots \, a_n$
Now we take the number $n + 1$.
We can form $n + 1$ permutations from this one by putting $n + 1$ in all places possible:
:$a_{n + 1} \, a_1 \, a_2 \, a_3 \, \ldots \, a_n, \quad a_1 \, a_{n + 1} \, a_2 \, a_3 \, \ldots \, a_n, \quad a_1 \, a_2 \, a_{n + 1} \, a_3 \, \ldots \, a_n, \quad \ldots, \quad a_1 \, a_2 \, a_3 \, \ldots \, a_n \, a_{n + 1}$
It is clear that all permutations of $n + 1$ objects can be obtained in this manner, and no permutation is obtained more than once.
As there are ${}^n P_n$ permutations on $n$ objects, there are $\paren {n + 1} \times {}^n P_n$ permutations on $n + 1$ objects.
Hence by induction, and the recursive definition of the factorial:
:${}^n P_n = n!$
{{qed}}
Theorem: Construction of Permutations

The ${}^n P_n$ permutations of $n$ objects can be generated algorithmically.
By Number of Permutations, that number is given by:
:${}^n P_n = n!$
where $n!$ denotes the factorial of $n$.
This will be demonstrated to hold.

Proof:
The following is an inductive method of creating all the permutations of $n$ objects.
=== Base Case ===
There is clearly one way to arrange one object in order.
=== Inductive Hypothesis ===
We assume that we have constructed all $n!$ permutations of $n$ objects.
=== Induction Step ===
{{WLOG}}, let a set $S_n$ of $n$ objects be $\left\{{1, 2, \ldots, n}\right\}$.
Take a permutation of $S_n$:
:$a_1 \, a_2 \, a_3 \, \ldots \, a_n$
Construct the array:
:$a_1 \, a_2 \, a_3 \, \ldots \, a_n \, \dfrac 1 2, \quad a_1 \, a_2 \, a_3 \, \ldots \, a_n \, \dfrac 3 2, \quad a_1 \, a_2 \, a_3 \, \ldots \, a_n \, \dfrac 5 2, \quad \ldots, \quad a_1 \, a_2 \, a_3 \, \ldots \, a_n \, \left({n + \dfrac 1 2}\right)$
This will contain $n + 1$ objects.
Now rename the elements of each permutation using the numbers $\left\{ {1, 2, \ldots, n}\right\}$ preserving order.
It is clear that all permutations of $n + 1$ objects can be obtained in this manner, and no permutation is obtained more than once.
As there are ${}^n P_n$ permutations on $n$ objects, there are $\left({n + 1}\right) \times {}^n P_n$ permutations on $n + 1$ objects.
Hence by induction, and the recursive definition of the factorial:
:${}^n P_n = n!$
{{qed}}
Theorem: De Polignac's Formula

Let $n!$ be the factorial of $n$.
Let $p$ be a prime number.
Then $p^\mu$ is a divisor of $n!$, and $p^{\mu + 1}$ is not, where:
:$\ds \mu = \sum_{k \mathop > 0} \floor {\frac n {p^k} }$
where $\floor {\, \cdot \,}$ denotes the floor function.

Proof:
Note that although the summation given in the statement of the theorem is given as an infinite sum, in fact it terminates after a finite number of terms (because when $p^k > n$ we have $0 < n/p^k < 1$).
From Number of Multiples less than Given Number, we have that $\floor{\dfrac n {p^k} }$ is the number of integers $m$ such that $0 < m \le n$ which are multiples of $p^k$.
We look more closely at $n!$:
:$n! = 1 \times 2 \times \ldots \times \paren {n - 1} \times n$
We see that any integer $m$ such that $0 < m \le n$ which is divisible by $p^j$ and not $p^{j + 1}$ must be counted exactly $j$ times.
That is:
:once in $\floor {\dfrac n p}$
:once in $\floor {\dfrac n {p^2} }$
$\ldots$
:once in $\floor {\dfrac n {p^j} }$
And that is all the occurrences of $p$ as a factor of $n!$.
Thus:
:$\mu = \floor {\dfrac n p} + \floor {\dfrac n {p^2} } + \dotsb + \floor {\dfrac n {p^j} }$
Hence the result.
{{qed}}
Theorem: Sum of Binomial Coefficients over Lower Index

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

Proof:
For all $n \in \N$, let $\map P n$ be the proposition:
:$\ds \sum_{i \mathop = 0}^n \binom n i = 2^n$
$\map P 0$ is true, as this just says $\dbinom 0 0 = 1$.
This holds by definition.
=== Basis for the Induction ===
$\map P 1$ is true, as this just says $\dbinom 1 0 + \dbinom 1 1 = 2$.
This holds by Binomial Coefficient with Zero and Binomial Coefficient with One (or Binomial Coefficient with Self).
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_{i \mathop = 0}^k \binom k i = 2^k$
Then we need to show:
:$\ds \sum_{i \mathop = 0}^{k + 1} \binom {k + 1} i = 2^{k + 1}$
=== Induction Step ===
This is our induction step:
{{begin-eqn}}
{{eqn | l = \sum_{i \mathop = 0}^{k + 1} \binom {k + 1} i
      | r = \binom {k + 1} 0 + \sum_{i \mathop = 1}^k \binom {k + 1} i + \binom {k + 1} {k + 1}
      | c = 
}}
{{eqn | r = \binom {k + 1} 0 + \sum_{i \mathop = 1}^k \paren {\binom k {i - 1} + \binom k i} + \binom {k + 1} {k + 1}
      | c = Pascal's Rule
}}
{{eqn | r = \paren {\sum_{i \mathop = 0}^{k - 1} \binom k i + \binom {k + 1} {k + 1} } + \paren {\binom {k + 1} 0 + \sum_{i \mathop = 1}^k \binom k i}
      | c = Translation of Index Variable of Summation
}}
{{eqn | r = \paren {\sum_{i \mathop = 0}^{k - 1} \binom k i + \binom k k} + \paren {\binom k 0 + \sum_{i \mathop = 1}^k \binom k i}
      | c = as $\dbinom {k + 1} {k + 1} = \dbinom k k = 1$ and $\dbinom {k + 1} 0 = \dbinom k 0 = 1$
}}
{{eqn | r = \sum_{i \mathop = 0}^k \binom k i + \sum_{i \mathop = 0}^k \binom k i
      | c = Translation of Index Variable of Summation
}}
{{eqn | r = 2^k + 2^k
      | c = 
}}
{{eqn | r = 2^{k + 1}
      | c = 
}}
{{end-eqn}}
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds \forall n \in \N: \sum_{i \mathop = 0}^n \binom n i = 2^n$
{{qed}}
Theorem: Sum of Binomial Coefficients over Lower Index

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

Proof:
Let $S$ be a set with $n$ elements.
From the definition of $r$-combination, $\ds \sum_{i \mathop = 0}^n \binom n i$ is the total number of subsets of $S$.
Hence $\ds \sum_{i \mathop = 0}^n \binom n i$ is equal to the cardinality of the power set of $S$.
Hence the result.
{{qed}}
Theorem: Sum of Binomial Coefficients over Lower Index

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

Proof:
From the Binomial Theorem, we have that:
:$\ds \forall n \in \Z_{\ge 0}: \paren {x + y}^n = \sum_{i \mathop = 0}^n \binom n i x^{n - i} y^i$
Putting $x = y = 1$ we get:
{{begin-eqn}}
{{eqn | l = 2^n
      | r = \paren {1 + 1}^n
      | c = 
}}
{{eqn | r = \sum_{i \mathop = 0}^n \binom n i 1^{n - i} 1^i
      | c = 
}}
{{eqn | r = \sum_{i \mathop = 0}^n \binom n i
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Alternating Sum and Difference of Binomial Coefficients for Given n

:$\ds \forall n \in \Z_{\geq 0}: \sum_{i \mathop = 0}^n \paren {-1}^i \binom n i = \delta_{n 0}$

Proof:
For $n > 0$:
{{begin-eqn}}
{{eqn | l = \sum_{i \mathop = 0}^n \paren{-1}^i \binom n i
      | r = \binom n 0 + \sum_{i \mathop = 1}^{n - 1} \paren{-1}^i \binom n i + \paren{-1}^n \binom n n
      | c = 
}}
{{eqn | r = \binom n 0 + \sum_{i \mathop = 1}^{n - 1} \paren{-1}^i \paren{\binom {n - 1} {i - 1} + \binom {n - 1} i} + \paren{-1}^n \binom n n
      | c = Pascal's Rule
}}
{{eqn | r = \binom n 0 - \sum_{i \mathop = 1}^{n - 1} \paren{\paren{-1}^{i-1} \binom {n - 1} {i - 1} - \paren{-1}^i \binom {n - 1} i} + \paren{-1}^n \binom n n
      | c =
}}
{{eqn | r = \binom n 0 - \paren{-1}^{1 - 1} \binom {n - 1} {1 - 1} + \paren{-1}^{n - 1} \binom {n - 1} {n - 1} + \paren{-1}^n \binom n n
      | c = Telescoping Series/Example 1
}}
{{eqn | r = 1 - 1 + \paren{-1}^{n - 1} - \paren{-1}^{n - 1}
      | c = Binomial Coefficient with Zero, Binomial Coefficient with Self
}}
{{eqn | r = 0
      | c =
}}
{{end-eqn}}
Hence the result.
{{qed}}
Theorem: Alternating Sum and Difference of Binomial Coefficients for Given n

:$\ds \forall n \in \Z_{\geq 0}: \sum_{i \mathop = 0}^n \paren {-1}^i \binom n i = \delta_{n 0}$

Proof:
Let $n > 0$.
From the Binomial Theorem, we have that:
:$\ds \forall n \in \Z_{\ge 0}: \paren {x + y}^n = \sum_{i \mathop = 0}^n  \binom n i x^{n - i} y^i$
Putting $x = 1, y = -1$, we get:
{{begin-eqn}}
{{eqn | l = 0
      | r = \paren {1 - 1}^n
      | c = which holds for all $n > 0$
}}
{{eqn | r = \sum_{i \mathop = 0}^n \binom n i 1^{n - i} \paren {-1}^i
      | c = 
}}
{{eqn | r = \sum_{i \mathop = 0}^n \paren {-1}^i \binom n i
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Alternating Sum and Difference of Binomial Coefficients for Given n

:$\ds \forall n \in \Z_{\geq 0}: \sum_{i \mathop = 0}^n \paren {-1}^i \binom n i = \delta_{n 0}$

Proof:
Let $n > 0$.
The assertion can be expressed:
:$\ds \sum_{i \mathop \le n} \paren {-1}^i \binom n i = 0$ for all $n > 0$
as $\dbinom n i = 0$ when $i < 0$ by definition of binomial coefficient.
From Alternating Sum and Difference of r Choose k up to n we have:
:$\ds \sum_{i \mathop \le n} \paren {-1}^i \binom r i = \paren {-1}^n \binom {r - 1} n$
Putting $r = n$ we have:
:$\ds \sum_{i \mathop \le n} \paren {-1}^i \binom n i = \paren {-1}^n \binom {n - 1} n$
As $n - 1 < n$ it follows from the definition of binomial coefficient that:
:$\dbinom {n - 1} n = 0$
{{qed}}
Theorem: Symmetry Rule for Binomial Coefficients

Let $n \in \Z_{>0}, k \in \Z$.
Then:
:$\dbinom n k = \dbinom n {n - k}$

Proof:
Follows directly from the definition of binomial coefficient, as follows.
If $k < 0$ then $n - k > n$.
Similarly, if $k > n$, then $n - k < 0$.
In both cases:
:$\dbinom n k = \dbinom n {n - k} = 0$
Let $0 \le k \le n$.
{{begin-eqn}}
{{eqn | l = \binom n k
      | r = \frac {n!} {k! \paren {n - k}!}
      | c = 
}}
{{eqn | r = \frac {n!} {\paren {n - k}! k!}
      | c = 
}}
{{eqn | r = \frac {n!} {\paren {n - k}! \paren {n - \paren {n - k} } !}
      | c = 
}}
{{eqn | r = \binom n {n - k}
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Symmetry Rule for Binomial Coefficients

Let $n \in \Z_{>0}, k \in \Z$.
Then:
:$\dbinom n k = \dbinom n {n - k}$

Proof:
From the definition of Cardinality of Set of Subsets, $\dbinom n k$ is the number of subsets of cardinality $k$ of a set with cardinality $n$.
Let $S$ be a set with cardinality $n$.
Let $\powerset S$ denote the power set of $S$.
Let $\AA_k \subseteq \powerset S$ be the set of elements of $\powerset S$ which have cardinality $k$.
For every $T \in \AA_k$ there exists its relative complement:
:$\relcomp S T \in \AA_{n - k}$
Define the mapping $f_k: \AA_k \to \AA_{n - k}$ as:
:$\forall T \in \AA_k: \map f T = \relcomp S T$
From Relative Complement Mapping on Powerset is Bijection it follows that $f_k$ is a bijection.
By definition of set equivalence, that means:
:$\card {A_k} = \card {A_{n - k} }$
That is, from the definition of Cardinality of Set of Subsets:
:$\dbinom n k = \dbinom n {n - k}$
{{qed}}
Theorem: Symmetry Rule for Binomial Coefficients

Let $n \in \Z_{>0}, k \in \Z$.
Then:
:$\dbinom n k = \dbinom n {n - k}$

Proof:
If we choose $k$ objects from $n$, then we leave $n - k$ objects.
Hence for every choice of $k$, we are also making the same choice of $n - k$.
Hence the number of choices of $k$ objects is the same as the number of choices of $n - k$ objects.
Hence the result.
{{qed}}
Theorem: Factors of Binomial Coefficient

For all $r \in \R, k \in \Z$:
:$k \dbinom r k = r \dbinom {r - 1} {k - 1}$
where $\dbinom r k$ is a binomial coefficient.
Hence:
:$\dbinom r k = \dfrac r k \dbinom {r - 1} {k - 1}$ (if $k \ne 0$)
and:
:$\dfrac 1 r \dbinom r k = \dfrac 1 k \dbinom {r - 1} {k - 1}$ (if $k \ne 0$ and $r \ne 0$)

Proof:
If $k = 0$ then $\dbinom r k = r \dbinom {r - 1} {k - 1} = 0$ by definition.
Otherwise:
{{begin-eqn}}
{{eqn | l = k \binom r k
      | r = k \frac {r^{\underline k} } {k!}
      | c = 
}}
{{eqn | r = k \frac {r \paren {r - 1} \paren {r - 2} \dotsm \paren {r - k + 1} } {k \paren {k - 1} \paren {k - 2} \dotsm 1}
      | c = 
}}
{{eqn | r = \frac {r \paren {r - 1} \paren {r - 2} \dotsm \paren {r - k + 1} } {\paren {k - 1} \paren {k - 2} \dotsm 1}
      | c = 
}}
{{eqn | r = r \frac {\paren {r - 1} \paren {r - 2} \dotsm \paren {\paren {r - 1} - \paren {k - 1} + 1} } {\paren {k - 1} \paren {k - 2} \dotsm 1}
      | c = 
}}
{{eqn | r = r \binom {r - 1} {k - 1}
      | c = 
}}
{{end-eqn}}
{{qed|lemma}}
If $k \ne 0$, we can divide both sides of:
:$k \dbinom r k = r \dbinom {r - 1} {k - 1}$
by $k$ to obtain:
:$\dbinom r k = \dfrac r k \dbinom {r - 1} {k - 1}$
{{qed|lemma}}
If $k \ne 0$ and $r \ne 0$, we can divide both sides of:
:$\dbinom r k = \dfrac r k \dbinom {r - 1} {k - 1}$
by $r$ to obtain:
:$\dfrac 1 r \dbinom r k = \dfrac 1 k \dbinom {r - 1} {k - 1}$
{{qed}}
Theorem: Sum of r+k Choose k up to n

:$\ds \forall n \in \Z: n \ge 0: \sum_{k \mathop = 0}^n \binom {r + k} k = \binom {r + n + 1} n$

Proof:
Proof by induction:
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition
:$\ds \sum_{k \mathop = 0}^n \binom {r + k} k = \binom {r + n + 1} n$
Theorem: Negated Upper Index of Binomial Coefficient

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

Proof:
{{begin-eqn}}
{{eqn | l = \binom r k
      | r = \frac {r^{\underline k} } {k!}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | r = \frac 1 {k!} \prod_{j \mathop = 0}^{k - 1} \paren {r - j}
      | c = {{Defof|Falling Factorial}}
}}
{{eqn | r = \frac {\paren {-1}^k} {k!} \prod_{j \mathop = 0}^{k - 1} \paren {-\paren {r - j} }
      | c = 
}}
{{eqn | r = \frac {\paren {-1}^k} {k!} \prod_{j \mathop = 0}^{k - 1} \paren {j - r}
      | c = 
}}
{{eqn | r = \frac {\paren {-1}^k} {k!} \prod_{j \mathop = 0}^{k - 1} \paren {\paren {k - 1} - j - r}
      | c = Permutation of Indices of Product
}}
{{eqn | r = \frac {\paren {-1}^k} {k!} \prod_{j \mathop = 0}^{k - 1} \paren {\paren {k - r - 1} - j}
      | c = 
}}
{{eqn | r = \paren {-1}^k \frac {\paren {k - r - 1}^{\underline k} } {k!}
      | c = {{Defof|Falling Factorial}}
}}
{{eqn | r = \paren {-1}^k \binom {k - r - 1} k
      | c = {{Defof|Binomial Coefficient}}
}}
{{end-eqn}}
{{qed}}
Theorem: Negated Upper Index of Binomial Coefficient

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

Proof:
{{begin-eqn}}
{{eqn | l = \binom {-r} k
      | r = \paren {-1}^k \binom {k - \paren {-r} - 1} k
      | c = Negated Upper Index of Binomial Coefficient
}}
{{eqn | r = \paren {-1}^k \binom {r + k - 1} k
      | c=
}}
{{end-eqn}}
{{qed}}