There is nothing more practical than a good theory, Leonid Brezhnev.

The Architecture of the Natural Numbers

When we first learn mathematics as children, we learn to count: $1, 2, 3, 4\dots$ and so on. We accept these numbers as self-evident facts of the universe. However, in formal mathematics, the natural numbers are not assumed; they are rigorously constructed from foundational logic.

A natural number is a mathematical object. It is a number that occurs commonly in nature. As such, it is a whole, non-negative number, that is, a member of the sequence $0, 1, 2, 3, \cdots,$ obtained by starting from zero and adding 1 successively.

The set of natural numbers, denoted by the blackboard bold symbol $\mathbb{N}$, represents the non-negative whole numbers: $\mathbb{N} = \{0, 1, 2, 3, \dots \}$

Is Zero a Natural Number? Whether zero is included in $\mathbb{N}$ is a matter of convention. Historically, number theorists started at $1$. However, in modern set theory, logic, and computer science, it is almost universally accepted to start at $0$. When authors wish to be explicit, they often write $\mathbb{N}_0 = \{0, 1, 2, \dots\}$ and $\mathbb{N}_1 = \{1, 2, 3, \dots\}$. In this article, we include $0$.

Building Something from Nothing: Von Neumann Ordinals

How do we mathematically define a number without referencing other numbers? In the early 20th century, John von Neumann provided a brilliant solution using pure set theory. He proposed that we can construct all natural numbers starting from absolute nothingness—the empty set, denoted by $\emptyset$ or $\{\}$.

We define the successor of a set $n$, denoted $s(n)$, as a set that contains everything inside $n$, plus $n$ itself: $\boxed{s(n) = n \cup \{n\}}$

Using this rule, we can build the numbers:

Zero is defined as the empty set: $0 = \emptyset = \{\}$
One is the successor of $0$: $1 = 0 \cup \{0\} = \emptyset \cup \{\emptyset\} = \{\emptyset\} = \{0\}$
Two is the successor of $1$:$2 = 1 \cup \{1\} = \{0\} \cup \{1\} = \{0, 1\}$
Three is the successor of $2$:$3 = 2 \cup \{2\} = \{0, 1\} \cup \{2\} = \{0, 1, 2\}$

Notice the profound elegance here: the number $3$ is literally a set containing exactly three elements. The number $n$ is simply the set of all natural numbers strictly less than $n$.

The Peano Axioms

To work with $\mathbb{N}$ algebraically, we rely on a set of rules formulated by Giuseppe Peano. Let there be a set $\mathbb{N}$ with a starting element $0$ and a successor function $s : \mathbb{N} \to \mathbb{N}$ (where you can intuitively think of $s(n)$ as $n+1$).

The core axioms are:

Zero is the starting point: $0 \in \mathbb{N}$, and there is no natural number $n$ such that $s(n) = 0$.
Injectivity: The successor function is one-to-one. If $s(n) = s(m)$, then $n = m$.
The Axiom of Induction: If a subset $M \subseteq \mathbb{N}$ contains $0$, and if $n \in M \implies s(n) \in M$, then the subset $M$ contains every natural number ($M = \mathbb{N}$).

Natural numbers can be added and multiplied, i.e., if $m$ and $n$ are natural numbers, then $m + n$ and $m \times n$ (aka $m \cdot n$ or $mn$) are also natural numbers. Zero is the additive identity for whole numbers, i.e., when zero is added to any whole number, the resultant number is the given whole number itself: $n + 0 = n, \forall n \in \mathbb{N}$, meaning for all $n$ numbers in the natural numbers.

Defining Addition

Using only the successor function, we can formally define addition via a recursive definition. For any $m, n \in \mathbb{N}$:

Base Rule: $m + 0 = m$
Recursive Rule: $m + s(n) = s(m + n)$

Writing $s(n)$ as $(n+1)$, the recursive rule looks more familiar: $m + (n+1) = (m+n) + 1$.

The Properties of Addition

From these two simple rules, we can prove every algebraic property of addition using mathematical induction.

Theorem 1: Addition is Associative. For all $x, y, z \in \mathbb{N}$, we have $x + (y + z) = (x + y) + z$.

Proof by Induction on $z$:

Base Case ($z = 0$): $x + (y + 0) = x + y = (x + y) + 0$. The base case holds trivially by the Base Rule of addition.

Inductive Step: Assume the property holds for $z$, so $x + (y + z) = (x + y) + z$. We must prove it for $z + 1$ (which is $s(z)$).

$$\begin{aligned} x + (y + s(z)) &= x + s(y + z) \quad &\text{[Recursive Rule on inner bracket]} \\ &= s(x + (y + z)) \quad &\text{[Recursive Rule on outer addition]} \\ &= s((x + y) + z) \quad &\text{[By Inductive Hypothesis]} \\ &= (x + y) + s(z) \quad &\text{[Recursive Rule applied backwards]} \end{aligned}$$

By the principle of induction, associativity holds for all $z \in \mathbb{N}$. ∎

Theorem 2: Addition is Commutative. For all $x, y \in \mathbb{N}$, we have $x + y = y + x$.

Proof by Induction:

Proving commutativity is surprisingly rigorous because our Base Rule ($m + 0 = m$) is asymmetrical. It doesn’t guarantee that $0 + m = m$. Therefore, we need two quick lemmas.

Lemma 1 ($0 + y = y$):

By induction on $y$. (i) Base case: $0 + 0 = 0$. (ii) Assume $0 + y = y$. For $s(y)$: $0 + s(y) = s(0 + y) = s(y)$. Lemma proven.

Lemma 2 ($s(x) + y = s(x + y)$):

By induction on $y$. (i) Base case: $s(x) + 0 = s(x) = s(x + 0)$. (ii) Assume true for $y$. For $s(y)$: $s(x) + s(y) = s(s(x) + y) = s(s(x + y)) = s(x + s(y))$. Lemma proven.

Now, we prove the main theorem, $x + y = y + x$, by induction on $y$:

Base Case ($y = 0$): $x + 0 = x = 0 + x \quad \text{[By Lemma 1]}$

Inductive Step: Assume $x + y = y + x$. We must prove it for $s(y)$.

$$\begin{aligned} x + s(y) &= s(x + y) \quad &\text{[By Recursive Rule of addition]} \\ &= s(y + x) \quad &\text{[By Inductive Hypothesis]} \\ &= s(y) + x \quad &\text{[By Lemma 2]} \end{aligned}$$

By the principle of induction, addition is completely commutative. ∎

Defining Multiplication

We define multiplication recursively, building it on top of addition. For any $m, n \in \mathbb{N}$:

Base Rule: $0 \cdot m = 0$
Recursive Rule: $s(n) \cdot m = (n \cdot m) + m$

Just like addition, multiplication is associative and commutative, and $1$ serves as the multiplicative identity ($1 \cdot m = m$). Perhaps most importantly, multiplication interacts with addition via the Distributive Law.

Theorem 3: The Distributive Law. For all $n, m, k \in \mathbb{N}$, we have $n \cdot (m + k) = (n \cdot m) + (n \cdot k)$.

Proof by Induction on $n$:

Base Case ($n = 0$): $0 \cdot (m + k) = 0 = 0 + 0 = (0 \cdot m) + (0 \cdot k)$
Inductive Step: Assume the property holds for $n$. We must prove it for $s(n)$, which we will write as $(n+1)$.

$$\begin{aligned} (n + 1) \cdot (m + k) &= [n \cdot (m + k)] + (m + k) \quad &\text{[Recursive Rule of mult.]} \\ &= (n \cdot m + n \cdot k) + (m + k) \quad &\text{[By Inductive Hypothesis]} \\ &= (n \cdot m + m) + (n \cdot k + k) \quad &\text{[By Assoc. \& Comm. of addition]} \\ &= (n+1)\cdot m + (n+1)\cdot k \quad &\text{[Recursive Rule applied backwards]} \end{aligned}$$

Thus, the distributive property holds for all natural numbers. ∎

Order and the Well-Ordering Principle

Natural numbers are naturally ordered. We define the relation $m \le n$ to mean that there exists some natural number $k$ such that $m + k = n$.

This ordering relation is:

Reflexive: $n \le n$ (since $n + 0 = n$).
Antisymmetric: If $n \le m$ and $m \le n$, then $n = m$.
Transitive: If $n \le l$ and $l \le m$, then $n \le m$.

Proof of Transitivity: If $n \le l$, there is some $k \in \mathbb{N}$ where $n + k = l$. If $l \le m$, there is some $k' \in \mathbb{N}$ where $l + k' = m$. Substituting $l$ into the second equation yields $(n + k) + k' = m$. By associativity, $n + (k + k') = m$. Since $k + k'$ is a natural number, by definition, $n \le m$. ∎

The most profound property of this ordering is the Well-Ordering Principle.

Theorem. The Well-Ordering Principle. Every non-empty subset of the natural numbers has a least (minimal) element.

While $\mathbb{N}$ is well-ordered, sets like the integers $\mathbb{Z}$ or real numbers $\mathbb{R}$ are not. The subset of all negative integers has no minimum element, as it goes to negative infinity.

Proof by Contradiction:

Suppose there exists a non-empty subset $S \subseteq \mathbb{N}$ that does not have a least element. Let $S^*$ be the complement of $S$ (the set of all natural numbers not in $S$). We will prove by strong induction that every natural number is in $S^*$.

Base Case: The number $0$ must be in $S^*$. Why? Because if $0$ were in $S$, it would automatically be the least element of $S$ (since $0$ is the smallest natural number). But $S$ has no least element. Thus, $0 \notin S$, meaning $0 \in S^*$.
Strong Inductive Step: Assume that all numbers $0, 1, 2, \dots, n$ are in $S^*$. This means none of these numbers are in $S$. What about $n+1$? If $n+1$ were in $S$, it would be the minimum element of $S$, because we just assumed all numbers smaller than it are excluded from $S$. But $S$ has no minimum element! Therefore, $n+1$ cannot be in $S$. Thus, $n+1 \in S^*$.

Application of the Well-Ordering Principle

We can use the Well-Ordering Principle as a substitute for induction.

Let’s prove that the sum of the first $n$ odd numbers is $n^2$: $1 + 3 + 5 + \dots + (2n - 1) = n^2$

Proof:

Suppose, for the sake of contradiction, the formula is false for some natural numbers. Let $S$ be the set of all $n$ where the formula fails.

By the Well-Ordering Principle, $S$ must have a minimum element. Let’s call it $k$.

Since the formula works for $n=1$ ($1 = 1^2$), we know $k \neq 1$, so $k > 1$.

Because $k$ is the absolute smallest number that fails the formula, the formula must perfectly work for the number right before it, $k-1$: $1 + 3 + \dots + (2(k-1) - 1) = (k-1)^2$

Let’s add the next odd number, $(2k - 1)$, to both sides of this valid equation:

$$\begin{aligned} 1 + 3 + \dots + (2k - 3) + (2k - 1) &= (k-1)^2 + (2k - 1) \\ &= (k^2 - 2k + 1) + 2k - 1 \\ &= k^2 \end{aligned}$$

We have just proven that the formula does work for $k$. But we defined $k$ as a number where the formula fails! This is a contradiction ($\bot$). Therefore, the set of failures $S$ must be empty, meaning the formula is true for all natural numbers.

Combinatorics, Pascal’s Triangle, and the Binomial Theorem

In combinatorics, the binomial coefficient is used to denote the number of possible ways to choose or pick $k$ elements from a larger set of size $n$. In the simplest terms, it is the number of ways of picking $k$ outcomes from $n$ possibilities.

Before we can expand algebraic polynomials, we must first understand how to count arrangements and selections. We break this down into permutations and combinations.

Permutation with Repetition. A permutation is an arrangement of objects in a particular way or a specific order.
Imagine a standard three-digit briefcase lock. The numbers range from $0$ to $9$, giving us $10$ options per dial. We need to select $k=3$ numbers from a pool of $n=10$ possibilities. Because the lock can have the code 7-7-7, repetition is allowed, and the order strictly matters (1-2-3 is not the same as 3-2-1).
The formula is simply $n^k$. For our lock, there are $10^3 = 1000$ possible permutations.
Permutation without Repetition.
What if repetition is impossible? Suppose we have $8$ athletes competing in a 100-meter dash (Alice, Bob, Charlie, …, Henry). How many ways can we award the Gold, Silver, and Bronze medals?
We have $8$ choices for the Gold medal. Once that is awarded, we only have $7$ choices for Silver, and $6$ choices for Bronze. Total permutations $= 8 \times 7 \times 6 = 336$.
Mathematically, we are selecting $k=3$ winners from $n=8$ competitors. We can calculate this by taking the factorial of the total number of people, and dividing it by the factorial of the “non-selected” people to cancel them out: $P(n, k) = \frac{n!}{(n-k)!}$
For our race: $P(8, 3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1} = 8 \times 7 \times 6 = 336$
In permutations without repetition, the order matters, but we cannot reuse elements.
Combinations.
A combination is a selection of $k$ items from a set of $n$ items such that we don't care about the order of selection. Repetition is not allowed. How can we give three diplomas to 8 people? Well, in this case, the order we pick people does not matter, so Diploma→Alice, Diploma→Bob, Diploma→Charlie is the same as giving to Diploma→Bob, Diploma→Alice, Diploma→Charlie, and so on. The general formula is C(n, k) = $\frac{n!}{(n-k)!k!}$; for our example, C(8, 3) $= \frac{8!}{5!3!} = 56$ where we just create all the permutations and divide by all the redundancies, that is, 3! ways to rearrange the three winners (those who receive the diplomas) and 5! ways to rearrange the losers.

Example. You are a disc jockey at a wild party. Select three love songs from a list of 10 romantic ballads. The order you play them doesn’t matter for the playlist selection. C(10, 3) = $\frac{n!}{(n-k)!k!} = \frac{10!}{(10-3)!3!} = 120$.

Definition. The value of the binomial coefficient for natural numbers $n$ and $k$ …

It is read as “$n$ choose $k$”, denoted as $C(n, k)$ or $\binom{n}{k}$,
It is given by $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ for $0 \le k \le n$. $\binom{n}{k} = 0$ if $k \gt n$.
It counts how many ways we can choose $k$ elements from $n$ distinct elements without repetition and without regard to order.
It makes sense because: (i) $n!$ counts all permutations of $n$ items. (ii) But combinations do not care about order, so we divide by: $k!$ to remove the ordering of the chosen $k$ items, $(n-k)!$ to remove the ordering of the unchosen items.

Pascal’s Triangle and Identity

Pascal’s triangle is a geometric arrangement of the binomial coefficients in a triangular grid, in which the $n$-th row contains the $n + 1$ possible values of $k$, that is, $\binom{n}{k}$. The numbers are placed in such a way that each number is the sum of the two entries or numbers just above it. It is used widely in probability theory, combinatorics, and algebra.

Pascal’s Triangle. Let $n$ and $k$ be natural numbers with $1 \le k \le n$. Then, the following formula applies, $\boxed{\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}}$

The Combinatorial Intuition

Imagine you need to select a committee of $k$ members from a group of $n+1$ people. Let’s single out one specific person: Alice.

Every possible committee either includes Alice or excludes Alice.

If we include Alice, we still need to choose $k-1$ members from the remaining $n$ people. This is $\binom{n}{k-1}$.
If we exclude Alice, we must choose all $k$ members from the remaining $n$ people. This is $\binom{n}{k}$.
Adding these two scenarios together gives us all possible committees: $\binom{n+1}{k}$.

The Algebraic Proof

$$\binom{n}{k-1} + \binom{n}{k} = \frac{n!}{(k-1)!(n - (k-1))!} + \frac{n!}{k!(n-k)!}$$$$= \frac{n!}{(k-1)!(n-k+1)!} + \frac{n!}{k!(n-k)!}$$

To add these fractions, we need a common denominator, which will be $k!(n-k+1)!$. We multiply the numerator and denominator of the first fraction by $k$, and the second fraction by $(n-k+1)$:

$= \frac{n! \cdot k}{k!(n-k+1)!} + \frac{n! \cdot (n-k+1)}{k!(n-k+1)!} = \frac{n!(k + n - k + 1)}{k!(n-k+1)!} = \frac{n!(n + 1)}{k!(n+1-k)!} = \frac{(n + 1)!}{k!(n+1-k)!} = \binom{n+1}{k}$

The Binomial Theorem

The Binomial Theorem dictates how to expand the algebraic powers of a binomial. Let $x$ and $y$ be real numbers, and $n$ be any natural number. The theorem states that $(x+y)^n$ can be expressed as the sum of $n+1$ terms: $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$.

The Intuition

Why do combinatorics apply to algebra? Consider $(x+y)^3$: $(x+y)(x+y)(x+y)$

To expand this, you must choose either an $x$ or a $y$ from each of the three parentheses, multiplying them together. How many ways can you create an $x^2y$ term? You must “choose” the $x$ from exactly $2$ out of the $3$ sets of parentheses. The number of ways to do this is “from 3 choose 2”, or $\binom{3}{2} = 3$. Thus, the coefficient of $x^2y$ is exactly $3$.

The Rigorous Proof (By Mathematical Induction)

Base Case: Let $n = 0$. $(x+y)^0 = 1$

$\sum_{k=0}^{0} \binom{0}{k} x^k y^{0-k} = \binom{0}{0} x^0 y^0 = 1 \cdot 1 \cdot 1 = 1$. The base case holds true.

Inductive Step: Assume the theorem holds true for a natural number $n$ (the inductive hypothesis). We must prove it holds for $n+1$. It is obviously a fact that $(x+y)^{n+1} = (x+y)(x+y)^n$

Substitute the inductive hypothesis for $(x+y)^n$: $= (x+y) \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$

Distribute the $(x+y)$: $= x \left( \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k} \right) + y \left( \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k} \right)$

Bring the $x$ and $y$ inside the summations by increasing their exponents by 1: $= \sum_{k=0}^{n} \binom{n}{k} x^{k+1} y^{n-k} + \sum_{k=0}^{n} \binom{n}{k} x^k y^{n+1-k}$

To combine these sums, we need the exponents of $x$ and $y$ to match. We will pull the very last term (where $k=n$) out of the first sum, and the very first term (where $k=0$) out of the second sum:

$$= \left( x^{n+1} + \sum_{k=0}^{n-1} \binom{n}{k} x^{k+1} y^{n-k} \right) + \left( \sum_{k=1}^{n} \binom{n}{k} x^k y^{n+1-k} + y^{n+1} \right)$$

Now, we perform an index shift on the first sum so its limits match the second sum. Let $j = k + 1$. Because $k$ runs from $0$ to $n-1$, our new index $j$ will run from $1$ to $n$. Substituting $k = j - 1$:

$$\sum_{j=1}^{n} \binom{n}{j-1} x^j y^{n-(j-1)} = \sum_{j=1}^{n} \binom{n}{j-1} x^j y^{n+1-j}$$

Because $j$ is just a dummy variable, we can safely rename it back to $k$:

$$= x^{n+1} + \sum_{k=1}^{n} \binom{n}{k-1} x^k y^{n+1-k} + \sum_{k=1}^{n} \binom{n}{k} x^k y^{n+1-k} + y^{n+1}$$

Now, both summations have the exact same limits and the exact same $x$ and $y$ terms, allowing us to combine them:

$$= x^{n+1} + \sum_{k=1}^{n} \left[ \binom{n}{k-1} + \binom{n}{k} \right] x^k y^{n+1-k} + y^{n+1}$$

Notice the terms inside the brackets. By Pascal’s Identity, we know that $\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$. Substituting this in:

$$= x^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k} x^k y^{n+1-k} + y^{n+1}$$

Finally, we can absorb the two dangling terms ($x^{n+1}$ and $y^{n+1}$) back into the summation. The $x^{n+1}$ term is exactly what we get if we evaluate the sum at $k=n+1$, and $y^{n+1}$ is what we get if we evaluate the sum at $k=0$. Thus, we can expand our limits to range from $0$ to $n+1$:

$$= \sum_{k=0}^{n+1} \binom{n+1}{k} x^k y^{(n+1)-k}$$

This is exactly the formulation of the theorem for $n+1$. By mathematical induction, the theorem is proven for all natural numbers $n$. $\blacksquare$

The Natural Numbers. The Binomial Theorem.