You can add to get to any Number
Let \( a, b \in \mathbb{ Z } \), then there exists some \( k \in \mathbb{ Z } \) such that \( a + k = b \)
If we want the equation to hold true, we require some \( k \in \mathbb{ Z } \) such that \( k = b - a \), since the integers are closed under subtraction, this value works as verfied by the fact that \( a + \left( b - a \right) = b \)
Numbers from Zero to K
Let \( k \in \mathbb{ N } _ 0 \) and define the set \( X _ k := \left\{ x \in \mathbb{ N } _ 0 : 0 \le x \le k \right\} \), then \( |X _ k| = k + 1 \)

We prove the claim by induction, for the base case if \( k = 0 \), then \( X _ k = \left\{ 0 \right\} \) thus \( |X _ k| = 1 = 0 + 1 = k + 1 \) as needed.

Let \( n \in \mathbb{ N } _ 1 \), and assume the claim holds for this value, now we want to prove it holds true for \( n + 1 \). We can see that \( X _ (n + 1) = \left\{ x \in \mathbb{ N } ^ 0 : 0 \le x \le n + 1 \right\} = X _ n \cup \left\{ n + 1 \right\} \), thus \( |X _ (n + 1)| = |X_n| + 1 = n + 1 \) as needed.

The Number of Integers between Two Integers Inclusive
Let \( a, b \in \mathbb{ Z } \) such that \( a \le b \) , then \( |\left\{ x \in \mathbb{ Z } : a \le x \le b \right\}| = b - a + 1 \)

We know that there is some \( k \in \mathbb{ Z } \) such that \( b = a + k \), therefore we're looking at the set \( \left\{ x \in \mathbb{ Z } : a \le x \le a + k \right\} \), this set is in clear bijection with the set \( \left\{ x \in \mathbb{ Z } : 0 \le x \le k \right\} \) through the function \( f \left( x \right) = x - a \), therefore our original set has \( k + 1 \), elements. Moreover \( k = b - a \) which completes the proof.

Pigeon Hole Principle
Suppose that \( f : X \to Y \) is between two finite sets and that \( |X| > |Y| \), then there exists some \( y \in Y \) and \( a \neq b \in X \) such that \( f \left( a \right) = f \left( b \right) = y \)
Catalan Numbers
Let \( n \in \mathbb{ N } _ 0 \), then the number of lattice paths from \( \left( 0, 0 \right) \) to \( \left( n, n \right) \) which never go above then line \( y = x \) is said to be the \( n \)-th Catalan Number
Formula For the \( n \)-th Catalan Number
\[ C \left( n \right) = \frac{1}{n + 1} \binom{2n}{n} \]
Bracket String
A bracket string is a finite tuple \( \left( a _ 1, \ldots a _ k \right) \) such that \( a _ i \in \left\{ \mathtt{(}, \mathtt{)} \right\} \)
For example "())))(" is a bracket string.
Valid Bracket String
A bracket string \( \left( a _ 1, \ldots , a _ k \right) \) is said to be valid by considering the mapping \( f : \left\{ \mathtt{(}, \mathtt{)} \right\} \to \left\{ -1, 1 \right\} \) such that for any \( j \in \left[ 1, \ldots k \right] \) \[ \sum _ { i = 1 } ^ j f \left( a _ i \right) \le 0 \text{ and } \sum _ { i = 1 } ^ k f \left( a _ i \right) = 0 \]
Bijection Between Valid Bracket Strings and Lattice Paths
For every valid bracket string involving \( n \) pairs of brackets, this corresponds to exactly one lattice path from \( \left( 0, 0 \right) \) to \( \left( n, n \right) \) which never crosses the diagonal.
Consider the construction of a lattice path \( l \) from a valid bracket string
  • If \( a _ i = \mathtt{(} \) then \( l _ i = R\)
  • If \( a _ i = \mathtt{)} \) then \( l _ i = U\)
We can prove that this is a lattice path not crossing the diagonal by the definition of valid bracket string.
Number of Valid Bracketings is Equal to the \( n \)-th Catalan Number
The number of distinct arrangement of \( n \) pairs of left-right parenthesis which close is equal to \( C \left( n \right) \)
This is true because we constructed a bijection valid bracket arrangments and lattice paths, the latter of which we know has size equal to \( C \left( n \right) \) as needed.
Counting Stars
Let \(S\) be a nonempty set, and \(*\) a binary operation on \(S\), called a star. If \(*\) is not known to be associative, the expression "the star of \(a, b, c\) " (for some \(a, b, c \in S\) ) is ambiguous. It could have one of 12 distinct interpretations: \[ \begin{array}{llll} (a * b) * c & a *(b * c) & (a * c) * b & a *(c * b) \\ (b * a) * c & b *(a * c) & (b * c) * a & b *(c * a) \\ (c * a) * b & c *(a * b) & (c * b) * a & c *(b * a) . \end{array} \] For every \(n \in \mathbb{Z}^{+}\), let \(M(n)\) denote the number of distinct interpretations of the expression "the star of \(a_1, a_2, \ldots, a_n\) " (where \(a_1, a_2, \ldots, a_n\) are arbitrary elements in \(S\) ). Show that \[ M(n)=\frac{(2 \left( n - 1 \right) )!}{\left( n - 1 \right) !} \]
One can count \( M \left( n \right) \) by first fixing a valid bracket arrangement and then permuting elements with that valid bracket arrangement, moreover note that the star of \( a _ 1, \ldots a _ n \) contains \( n - 2 \) bracket pairs.