Peano Axioms Explained: Natural Numbers Made Rigorous

The natural numbers can be defined rigorously through the Peano axioms, a system built from a set, a successor function, and a starting element (0 or 1 depending on convention). This article, based on Anderson-Feil Chapter 1.1, covers the Peano axioms, how addition, multiplication, and exponentiation are defined recursively from them, a set-theoretic construction of the natural numbers, and closes with the Fibonacci number formula and several combinatorial identities from the same chapter’s exercises.

Key Takeaways

• A Peano system requires exactly three axioms: no element maps to 0 under the successor function, the successor function is injective, and the induction axiom holds.
• Any two Peano systems are related by a unique bijection that preserves the successor function and the starting element, meaning the natural numbers are unique “up to renaming.”
• The three Peano axioms are independent of one another: dropping any single one allows structures that satisfy the remaining two but fail the third, including infinite half-lines, finite cyclic sets, and truncated sequences.
• The natural numbers can be constructed purely from set theory by defining 0 as the empty set and each successor as n ∪ {n}, with the full set of naturals defined as the smallest inductive set.
• Gödel’s incompleteness results mean the consistency of the Peano axioms cannot be proven from within the system itself; it can only be shown relative to another system, such as set theory.
• The closed-form Fibonacci formula, F_n = ((1+√5)^n − (1−√5)^n)/(2^n√5), can be derived either by guessing a solution of the form CA^n + DB^n or by diagonalizing the recursion’s associated matrix.

Is zero a natural number?

Whether zero counts as a natural number is a genuinely contested question with no settled answer across the field. Many mathematicians working in foundational areas include zero, while a comparable number of mathematicians exclude it. The choice is essentially a matter of definition and makes little practical difference either way. This article follows the convention that 0 is a natural number, which is the opposite of the convention Anderson and Feil use in their text.

What are the Peano axioms?

Anderson and Feil describe the natural numbers intuitively without giving a fully rigorous treatment. The Peano axioms, named after the mathematician who formulated them, provide that rigorous foundation for the natural number system.

A Peano system consists of a set $N$, a function $s:N\rightarrow N$ called the successor function, and a distinguished element $0\in N$. These three components must satisfy the following properties:

• There is no $n\in N$ such that $s(n) = 0$.
• The function $s$ is injective.
• If $G\subseteq N$ is a set such that $1\in G$ and such that $s(n)\in G$ whenever $n\in G$, then $G=N$.

It is clear intuitively that the natural numbers satisfy these three axioms. A natural follow-up question is whether additional axioms are needed to fully pin down the natural numbers. The categoricity result covered later in this article shows that no further axioms are required.

How are addition, multiplication, and exponentiation defined in a Peano system?

Fix a Peano system $\mathbb{N}$ with successor function $s$ and distinguished element $0$. Addition, multiplication, and exponentiation can all be built recursively from just these two pieces of data.

Addition $+$ is defined recursively as the operation such that:

• $n+0 = n$
• $n + s(m) = s(n+m)$

Defining $1 = s(0)$ makes it straightforward to prove that $s(n) = n+1$, confirming that the successor function does pick out the next element in sequence.

The following properties of addition can be proven from the recursive definition:

• For all $n,m,k \in \mathbb{N}$, $n+(m+k) = (n+m) + k$ (associativity).
• For all $n,m\in \mathbb{N}$, $n+m = m+n$ (commutativity).
• For all $n\in \mathbb{N}$, $n+0 = 0+n = n$.
• For all $n,m,k\in \mathbb{N}$, $n+k = m+k$ if and only if $n=m$ (cancellation).

These proofs are left as exercises; readers can also consult the opening sections of Bloch’s The Real Numbers and Real Analysis for worked versions.

Multiplication $\cdot$ is defined recursively as the operation such that:

• $n\cdot 0 = 0$
• $n\cdot s(m) = n\cdot m + n$

From this definition, the following can be proven:

• For all $n,m,k\in \mathbb{N}$, $n\cdot (m\cdot k) = (n\cdot m)\cdot k$.
• For all $n,m,k\in \mathbb{N}$, $n\cdot m = m\cdot n$.
• For all $n\in \mathbb{N}$, $n\cdot 1 = n = 1\cdot n$.
• For all $n,m,k\in \mathbb{N}$ such that $k\neq 0$, $n\cdot k = m\cdot k$ if and only if $n=m$.
• For all $n,m\in \mathbb{N}$, $n\cdot m = 0$ if and only if $n=0$ or $m=0$ (or both).
• For all $n,m,k\in \mathbb{N}$, $n\cdot (m+k) = n\cdot m + n\cdot k$ and $(m+k)\cdot n = m\cdot n + k\cdot n$ (distributivity).
• For all $n,m\in \mathbb{N}$, $n\cdot m = 1$ if and only if $n=m=1$.

Again, these are best worked through as exercises or found in Bloch’s text.

Exponentiation is defined recursively as:

• $n^0 = 1$
• $n^{s(m)} = n^m \cdot n$

From this it can be shown that:

• For all $n\in \mathbb{N}$, $n^1 = n$.
• For all $n,m,k\in \mathbb{N}$, $n^{m+k} = n^m \cdot n^k$.
• For all $n,m,k\in \mathbb{N}$, $n^{m\cdot k} = (n^m)^k = (n^k)^m$.
• For all $n,m,k \in \mathbb{N}$, $(n\cdot m)^k = n^k\cdot m^k$.

An ordering $\leq$ can also be defined: $n\leq m$ if and only if there is some $k$ such that $n+k = m$. From this definition, the following can be proven:

• For all $n\in \mathbb{N}$, $n\leq n$.
• For all $n,m\in \mathbb{N}$, $n\leq m$ and $m\leq n$ implies $n=m$.
• For all $n,m,k\in \mathbb{N}$, $n\leq m$ and $m\leq k$ implies $n\leq k$.
• For all $n,m\in \mathbb{N}$, either $n\leq m$ or $m\leq n$ (or both, which happens only when $n=m$).
• For all $n,m,k,l\in \mathbb{N}$, $n\leq k$ and $m\leq l$ implies $n+m\leq k+l$.
• For all $n,m,k,l\in \mathbb{N}$, $n\leq k$ and $m\leq l$ implies $n\cdot m \leq k\cdot l$.
• For all $n,m\in \mathbb{N}$, $n\leq m\leq n+1$ implies $n=m$ or $n+1 = m$.

The strict ordering $<$ is then defined as $n<m$ if and only if $n\leq m$ is true and $n=m$ is not. This ordering satisfies analogous properties, which readers should formulate and prove themselves.

Subtraction can also be defined: if $n\leq m$, then $m-n$ is defined as the number such that $n+(m-n) = m$. It can be proven that $m-n$ is well-defined, meaning there is exactly one number $k$ such that $n+k = m$.

Are the Peano axioms categorical, meaning is there only one structure that satisfies them?

The Peano axioms identify the natural numbers essentially uniquely, meaning there is only one structure (up to relabeling) that satisfies them. The word “essentially” matters because pure uniqueness can never come purely out of an axiomatic treatment. For example, $\mathbb{N}$ satisfies the Peano axioms, but so does the set ${0,2,4,6,8,…}$ if the successor function is defined as $s(n) = n+2$. This second example is simply a relabeling of the first, not an essentially different structure.

Formally: if $N$ is a Peano system with successor function $s$ and distinguished element $0$, and $M$ is a Peano system with successor function $t$ and distinguished element $a$, then there exists a unique bijection $f:N\rightarrow M$ such that $f(s(n)) = t(f(n))$ for all $n\in N$ and $f(0) = a$. This function performs the relabeling, in the sense that $f(n)$ is just another name for $n$.

The set ${0,2,4,6,8,…}$ also being a valid model for the Peano axioms can seem confusing, since it clearly is not the natural numbers as commonly understood. Under the Peano-system operations, however, $2\cdot 2$ works out differently than expected:

$$2\cdot 2 = 2\cdot s(0) = 2\cdot 0 + 2 = 0 + 2 = 2.$$

Viewed as a Peano system, the operations on ${0,2,4,6,8,…}$ are completely different from the ones normally associated with that set; the structure behaves as if 2 were simply another name for 1. Imagine a parallel universe where one is denoted 2, two is denoted 4, and so on. That is exactly the universe described by the Peano system ${0,2,4,6,8,…}$. People in that universe would find the familiar system of 0, 1, 2, 3, 4… just as strange.

Are the three Peano axioms independent of each other?

It is a useful exercise to show that the three Peano axioms are independent, meaning that assuming any two of them true does not allow the third to be proven. Here is how to demonstrate this for each pair:

1. Axioms 1 and 2 true, induction false: Consider the structure $[1,+\infty)$ with $s(x) = x+1$. The function $s$ is injective and no $x$ satisfies $s(x) = 1$, but the induction axiom fails. The subset $\mathbb{N} = {1,2,3,…}$ contains 1 and is closed under the successor function, yet it is not the entire set $[1,+\infty)$. This shows the induction axiom effectively limits the size of the system to the smallest one satisfying the first two axioms.
2. Axiom 1 and induction true, axiom 2 false: Take $X = {1,2,…,n}$ with $s(1) = 2$, $s(2) = 3$, and so on up to $s(n-1) = n$, but additionally define $s(n) = 2$. The first axiom and induction both hold, but $s$ is not injective since $s(n) = s(1) = 2$.
3. Axiom 2 and induction true, axiom 1 false: Take $X = {1,…,n}$ with the same successor definitions as above except that $s(n) = 1$, creating a cyclic structure. This example is mathematically useful because it describes divisibility, and many natural-number theorems carry over to this cyclic context, giving rise to cyclic groups and rings.

How can the natural numbers be constructed purely from set theory?

A Peano system can be built using only sets, taking the “first element” to be 0. The idea is that $0 = \emptyset,~1 = {\emptyset},~2 = {\emptyset,{\emptyset}},…$. In general, $0=\emptyset$, and if $n$ has been defined, then $n+1 = n\cup {n}$.

More formally, a set $X$ is called inductive if $\emptyset \in X$ and, for every $x\in X$, the set $x\cup{x}$ is also in $X$. It is an axiom of set theory that an inductive set exists. The set of natural numbers is then defined as the smallest inductive set: $\mathbb{N}=\bigcap{X~\vert~X~\text{is inductive}}.$

This set $\mathbb{N}$, with $0 = \emptyset$ and $s(x) = x\cup {x}$, can be checked against each Peano axiom:

1. No element maps to 0: If some $n\in \mathbb{N}$ satisfied $s(n) = 0$, then $n\cup {n} = \emptyset$, which would require $n\in \emptyset$. That is impossible.
2. Injectivity: First, every $n\in \mathbb{N}$ is transitive, meaning that if $m\in n$ then $m\subseteq n$. Let $X\subseteq \mathbb{N}$ be the set of transitive elements. Since $\emptyset$ is inductive, $\emptyset \in X$. If $n\in X$, then for $m\in n\cup {n}$, either $m=n$ (so $m\subseteq n\cup{n}$) or $m\in n$, in which case $m\subseteq n$ by transitivity. So $X$ is inductive and equals $\mathbb{N}$.

   Now assume $s(n) = s(m)$, so $n\cup {n} = m\cup {m}$. If $n\neq m$, then $n\in m$ and $m\in n$, which by transitivity forces $n\in n$. It can be shown this is impossible for any $n\in \mathbb{N}$ by taking $X$ to be the set of $n$ with $n\notin n$; $\emptyset\in X$, and if $n\notin n$, neither $n\cup{n}\in n$ nor $n\cup{n}=n$ can hold, so $n\cup{n}\in X$ too. Hence $X=\mathbb{N}$, and the successor function is injective.

3. Induction: If $G\subseteq \mathbb{N}$ contains 0 and is closed under the successor function, then $G$ is inductive, and since $\mathbb{N}$ is the smallest inductive set, $G=\mathbb{N}$.

What is a natural number, philosophically speaking?

Two definitions of the natural numbers have now been given: one as a set satisfying the Peano axioms, and one as an explicit set-theoretic construction where, for instance, $1 = {\emptyset}$. This construction can feel strange, since the number 1 seems intuitively like something different from a set containing the empty set.

The nature of what a number “really is” remains a philosophical and debatable question. What mathematicians care about in practice is which properties the natural numbers have, and it is broadly agreed that whatever the natural numbers are, they should satisfy the Peano axioms. Rather than settling what natural numbers are, mathematicians construct a model that behaves exactly like them, which has the benefit of requiring nothing beyond set theory to discuss natural numbers.

Are the Peano axioms consistent?

Consistency means an axiom system cannot lead to a contradiction, where a contradiction is a statement provable as both true and false. Consistency is essential: consider a toy axiom system requiring a set $X$ to be both nonempty and empty. No such system exists, since the axioms directly contradict each other. This illustrates that not every collection of axioms is automatically safe; any axiomatic system risks being similarly contradictory.

Gödel showed that no axiomatic system can prove its own consistency from within itself, so the Peano axioms’ consistency can only be discussed relative to another system. Within set theory, the Peano axioms can be shown consistent: if set theory is consistent, so are the Peano axioms, and the set-theoretic construction described above is one way of demonstrating this.

A Peano system is more than a formalized version of everyday counting numbers, because it asserts that infinitely many such numbers exist. While the numbers 1, 2, and 3 behave as expected from everyday experience, there is no direct experiential guarantee that a number as large as $10^{10^{10}}$ exists, since such enormous numbers do not exist in physical reality. Because these numbers exist only as abstractions, nothing guarantees in advance that the full infinite collection forms a consistent whole; it must instead be established relative to another consistent system, as described above.

How is the closed-form Fibonacci number formula derived?

Anderson and Feil define the Fibonacci numbers $F_n$ by $F_0 = 0$, $F_1 = 1$, and $F_{n+2} = F_{n+1} + F_n$ for $n\in \mathbb{N}$, then state without derivation the closed-form formula $F_n = \frac{(1+ \sqrt{5})^n – (1 – \sqrt{5})^n}{2^n \sqrt{5}}$. Two methods for deriving this formula are given below: one relying on an educated guess, and a more general one using linear algebra.

Method 1: guessing the exponential form

The guess is that a recursion of this type has a general solution of the form $CA^n + DB^n$ for constants $A,B,C,D\in \mathbb{R}$. There is no obvious reason this form should work, but it does for this recursion and many similar ones, as the linear algebra method in Method 2 confirms more generally.

Assuming $F_n = CA^n + DB^n$ for $n=0$ and $n=1$ gives $0 = C+D$ and $1 = CA + DB$. Since $C=-D$, this yields $1 = D(B-A)$, so $D\neq 0$ and $A\neq B$.

Requiring $F_{n+2} = F_{n+1} + F_n$ for $F_n = D(B^n – A^n)$ leads, after dividing by $D$, to $B^n(B^2 – B -1) = A^n(A^2 – A – 1)$ for all $n$.

Lemma: For real numbers $x,y,\alpha,\beta$ with $x$ and $y$ nonzero, if $\alpha x^n = \beta y^n$ for two consecutive integers $n$, then either $x=y$ or $\alpha = \beta=0$.

Proof: For consecutive integers $k$ and $k+1$, $\alpha x^k = \beta y^k$ and $\alpha x^{k+1}= \beta y^{k+1}$, giving $\beta y^{k+1} = \alpha y^k x$, so $\beta y = \alpha x$ (using $y\neq 0$).

If $\alpha=0$, then $\beta y=0$ forces $\beta=0$ as well. Otherwise, $\beta = \frac{\alpha x}{y}$, and substituting back gives $x^{n-1} = y^{n-1}$. Choosing $n$ so that $n-1$ is odd (possible since either $k$ or $k+1$ is even) and taking the odd root gives $x=y$. QED. The proof holds even if the equality is assumed for only two consecutive natural numbers.

Applying the lemma to $B^n(B^2 – B -1) = A^n(A^2 – A – 1)$ for all natural numbers leaves three cases. If $B=0$, then $F_n = CA^n$ with $C=0$ from $n=0$, forcing $F_n=0$ for all $n$, contradicting $F_1=1$. The case $A=0$ fails similarly. The remaining case requires $B^2 – B – 1 = A^2 – A – 1 = 0$, meaning $A$ and $B$ are the two distinct roots of $x^2-x-1=0$, namely $\frac{1+\sqrt{5}}{2}$ and $\frac{1-\sqrt{5}}{2}$.

From $D(B-A)=1$ with these values, $1 = -\sqrt{5}D$, so $D=-\frac{1}{\sqrt{5}}$ and $C=\frac{1}{\sqrt{5}}$, giving

$F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n – \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n,$

matching the claimed formula.

Method 2: matrix diagonalization

The second method avoids guessing the form $CA^n + DB^n$ by rewriting the recursion as a matrix equation. The relation $F_{n+2} = F_{n+1} + F_n$ can be written as

$\left(\begin{array}{c}F_{n+2}\\ F_{n+1}\end{array}\right)=\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)\left(\begin{array}{c}F_{n+1}\\ F_n\end{array}\right).$

Iterating this relation eventually gives

$\left(\begin{array}{c}F_{n+2}\\ F_{n+1}\end{array}\right)=\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)^{n+1}\left(\begin{array}{c} 1 \\ 0\end{array}\right).$

Diagonalizing the matrix $\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)$ requires solving the same characteristic equation $x^2 – x – 1 = 0$ found in Method 1, giving eigenvalues $\frac{1\pm \sqrt{5}}{2}$. Using the diagonalization

$\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right) = \left(\begin{array}{cc} \frac{1 – \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2}\\ 1 & 1\end{array}\right)\left(\begin{array}{cc} \frac{1 -\sqrt{5}}{2} & 0\\ 0 & \frac{1 + \sqrt{5}}{2} \end{array}\right)\left(\begin{array}{cc} – \frac{1}{\sqrt{5}} & \frac{5 + \sqrt{5}}{10}\\ \frac{1}{\sqrt{5}} & \frac{5 – \sqrt{5}}{10}\end{array}\right)$

and the fact that $A^n = X D^n X^{-1}$ when $A = XDX^{-1}$, one arrives at

$\begin{eqnarray*} \left(\begin{array}{c}F_{n+2}\\ F_{n+1}\end{array}\right) & = & \left(\begin{array}{cc} \frac{1 – \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2}\\ 1 & 1\end{array}\right)\left(\begin{array}{cc} \frac{1 -\sqrt{5}}{2} & 0\\ 0 & \frac{1 + \sqrt{5}}{2}\end{array}\right)^{n+1}\left(\begin{array}{cc} – \frac{1}{\sqrt{5}} & \frac{5 + \sqrt{5}}{10}\\ \frac{1}{\sqrt{5}} & \frac{5 – \sqrt{5}}{10}\end{array}\right)\left(\begin{array}{c}1 \\ 0 \end{array}\right)\\ & = & \left(\begin{array}{cc} \frac{1 – \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2}\\ 1 & 1\end{array}\right)\left(\begin{array}{cc} \left(\frac{1 -\sqrt{5}}{2}\right)^{n+1} & 0\\ 0 & \left(\frac{1 + \sqrt{5}}{2}\right)^{n+1} \end{array}\right)\left(\begin{array}{c} – \frac{1}{\sqrt{5}}\\ \frac{1}{\sqrt{5}}\end{array}\right)\\ & = & \left(\begin{array}{cc} \frac{1 – \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2}\\ 1 & 1\end{array}\right)\left(\begin{array}{c} -\frac{1}{\sqrt{5}}\left(\frac{1 -\sqrt{5}}{2}\right)^{n+1}\\ \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+1}\end{array}\right)\\ & = & \left(\begin{array}{c} \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+2} -\frac{1}{\sqrt{5}}\left(\frac{1 -\sqrt{5}}{2}\right)^{n+2}\\ \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+1} -\frac{1}{\sqrt{5}}\left(\frac{1 -\sqrt{5}}{2}\right)^{n+1}\end{array}\right) \end{eqnarray*}$

which reproduces the same closed-form solution.

Exercises:

• Find the general form of the Lucas numbers defined by $L_0 = 2$, $L_1 = 1$ and $L_{n+2}= L_{n+1} + L_n$. Use both methods to find the answer.
• Find the general form of the numbers defined by $A_0 = 2$, $A_1 = 4$ and $A_{n+2} = 5A_{n+1} + 3A_n$. Use both methods to find the answer.
• Find the general form of the numbers defined by $B_0 = 0$, $B_1 = 0$, $B_2 = 1$ and $B_{n+3} = B_{n+2} + B_{n+1} + B_n$. Adapt both methods to also deal with this more general case.

How are summation formulas for powers (exercises 1, 2, 6) derived without induction?

Exercises 1, 2, and 6 ask for proofs of formulas of the form $1^k + 2^k + 3^k + 4^k + … + n^k = …$ for a fixed exponent $k$: $k=1$ in exercise 1, $k=2$ in exercise 2, and $k=3$ in exercise 6.

An induction proof can confirm such a formula is true without revealing how it was originally found. This is a genuine limitation of induction proofs: they don’t generalize or suggest related results, which is why many mathematicians prefer non-induction derivations wherever possible.

A non-induction approach derives the value of $1^{k+1} + 2^{k+1}+ … n^{k+1}$ from $1^k + 2^k + … + n^k$, starting from the trivial identity $1^0 + 2^0 + … + n^0 = n$ and building upward through each exercise in turn.

Assuming the known formulas $1 + 1 + … + 1 = n$, $1 + 2 + … + n = \frac{n(n+1)}{2}$, and $1^2 + 2^2 + … + n^2 = \frac{n(2n+1)(n+1)}{6}$, the sum $1^3 + 2^3 + … + n^3$ can be computed without knowing it in advance. The method uses the binomial expansion $(a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4 ab^3 + b^4$, giving

$(m+1)^4 – m^4 = (m^4 + 4m^3 + 6m^2 + 4m + 1) – m^4 = 4m^3 + 6m^2 + 4m + 1$

A telescoping sum gives

$\begin{eqnarray*} \sum_{m=1}^n[(m-1)^4 – m^4] & = & (2^4 – 1^4) + (3^4 – 2^4) + … + ((n+1)^4 – n^4)\\ & = & (n+1)^4 – 1 \end{eqnarray*}$

while expanding the same sum term by term gives

$\begin{eqnarray*} \sum_{m=1}^n[(m-1)^4 – m^4] & = & \sum_{m=1}^n [4m^3 + 6m^2 + 4m + 1]\\ & = & 4\sum_{m=1}^n m^3 + 6\sum_{m=1}^n m^2 + 4\sum_{m=1}^n m + \sum_{m=1}^n 1\\ & = & 4\sum_{m=1}^n m^3 + 6\frac{n(2n+1)(n+1)}{6} + 4\frac{n(n+1)}{2} + n \end{eqnarray*}$

Equating the two expressions and isolating $\sum_{m=1}^n m^3$ gives

$\begin{eqnarray*} \sum_{m=1}^n m^3 & = & \frac{1}{4}\left((n+1)^4 – 1 – 6\frac{n(2n+1)(n+1)}{6} – 4\frac{n(n+1)}{2} – n\right)\\ & = & \frac{1}{4}\left((n^4 + 4n^3 + 6n^2 + 4n +1) – 1 – n(2n+1)(n+1) – 2n(n+1) – n\right)\\ & = & \frac{1}{4}\left((n^4 + 4n^3 + 6n^2 + 4n +1) – 1 – (2n^3 + 3n^2 + n) – (2n^2 + 2n) – n\right)\\ & = & \frac{1}{4}\left(n^4 + 2n^3 + n^2 \right)\\ & = & \frac{1}{4} n^2(n+1)^2 \end{eqnarray*}$

Exercises:

• Use the same technique to find $1 + 2 + … + n$ by only assuming the (trivial) identity $1^0 + 2^0 + … + n^0 = n$.
• Use the same technique to find $1^2 + 2^2 + … + n^2$ by only assuming the (trivial) identity $1^0 + 2^0 + … + n^0 = n$ and $1+ 2 +… + n = \frac{n(n+1)}{2}$.
• Find $1^4 + 2^4 + … + n^4$.

How is the telescoping sum in exercise 8 derived using partial fractions?

Exercise 8 asks for a proof of a formula for $\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + … +\frac{1}{n(n+1)}$. The technique used to find this formula is partial fraction decomposition, familiar from integration.

Decomposing $\frac{1}{k(k+1)}$ as $\frac{A}{k} + \frac{B}{k+1}$ leads to $(A+B) = 0$ and $A = 1$, giving $A=1$ and $B=-1$, so

$\frac{1}{k(k+1)} = \frac{1}{k} – \frac{1}{k+1}.$

This produces a telescoping sum:

$\begin{eqnarray*} \frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + … +\frac{1}{n(n+1)} & = & \left(\frac{1}{1} – \frac{1}{2}\right)+\left(\frac{1}{2} – \frac{1}{3}\right)+ … + \left(\frac{1}{n} – \frac{1}{n+1}\right)\\ & = & 1 – \frac{1}{n+1} \end{eqnraised*}$

which is the desired formula.

What does the binomial coefficient in exercise 14 mean combinatorially?

Exercise 14 introduces the binomial coefficient as $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. Beyond this algebraic definition, $\binom{n}{k}$ counts the number of $k$-element subsets of a set with $n$ elements. Two proofs of this fact follow: one combinatorial, one more formal.

Combinatorial proof

Selecting a $k$-element subset from a set $X$ with $n$ elements can be done by picking a first element ($n$ ways), then a second from the remaining $n-1$ elements, and so on until the $k$th element is picked from the remaining $n-k+1$ elements. This gives $n(n-1)…(n-k+1) = \frac{n!}{(n-k)!}$ ordered selections. Since each unordered subset of $k$ elements has been counted $k!$ times (once for each ordering), dividing by $k!$ gives $\frac{n!}{k!(n-k)!}$ subsets.

Formal proof

Let $X$ be a set with $n$ elements, and let $\Omega$ be the set of pairs $(A,f)$ where $A\subseteq X$ has $k$ elements and $f$ is a bijection between $A$ and ${1,…,k}$. Counting $\Omega$ two ways gives $|\Omega| = \binom{n}{k}k!$ (choosing the subset, then a bijection) and $|\Omega| = \frac{n!}{(n-k)!}$ (choosing an injection from ${1,…,k}$ into $X$ directly). Equating these gives $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

Exercises using this formal technique:

• Show that the number of injections from a set $A$ with $|A|=n$ into a set $B$ with $|B|=k$ (assuming $A\subseteq B$) is $\frac{n!}{(n-k)!}$ by considering the set $\Omega = {(f,g)~\vert~f~\text{is an injection}~A\rightarrow B~\text{and}~g~\text{is an injection}~B\setminus A\rightarrow B\setminus f(A)}$.
• Let $S$ be a set with subset groups $A_1,…,A_m$ (each of size $p$, with each element of $S$ in exactly $p_1$ of them) and $B_1,…,B_n$ (each of size $q$, with each element of $S$ in exactly $q_1$ of them). Express $n$ in terms of $m$, $p$, $p_1$, $q$, and $q_1$.

What is the multinomial theorem?

The multinomial theorem generalizes the binomial theorem to more than two terms:

$(x_1 + … + x_k)^n = \sum \binom{n}{n_1,…,n_k} x^{n_1} … x^{n_k}$

where the sum ranges over tuples $(n_1,…,n_k)$ of natural numbers with $n_1 + … + n_k = n$, and the multinomial coefficient is $\binom{n}{n_1,…,n_k} = \frac{n!}{n_1!…n_k!}$.

Exercises:

• Prove the multinomial theorem by induction.
• Interpret the multinomial coefficient combinatorially.
• Prove the multinomial theorem combinatorially.
• Prove that $\binom{n}{k} = \binom{n}{k,n-k}$.
• Note that also $\binom{n}{n-k} = \binom{n}{k,n-k}$, which proves $\binom{n}{k} = \binom{n}{n-k}$. Prove this formula also combinatorially.

Frequently Asked Questions

Is zero considered a natural number?

There is no universal agreement. Many mathematicians in foundational areas count zero as a natural number, while a comparable number exclude it. The distinction is a matter of convention and has little mathematical consequence either way.

What three axioms define a Peano system?

A Peano system requires that no element maps to the starting element under the successor function, that the successor function is injective, and that the induction axiom holds: any subset containing the starting element and closed under the successor function must be the entire set.

Are all Peano systems essentially the same?

Yes. Any two Peano systems are connected by a unique bijection that preserves the successor function and the starting element, meaning they differ only by relabeling, not by structure.

Can the Peano axioms be proven consistent?

Not from within the system itself. Gödel showed no axiomatic system can prove its own consistency. The Peano axioms can only be shown consistent relative to another system, such as set theory, using a construction like the one where 0 is the empty set and each successor is n ∪ {n}.

How is the closed-form Fibonacci formula derived?

One method guesses a solution of the form CA^n + DB^n and solves for the constants using the initial conditions F_0=0 and F_1=1, arriving at A and B as the two roots of x^2−x−1=0. A second, more general method diagonalizes the matrix associated with the recursion and reaches the same result.

What does the binomial coefficient count?

The binomial coefficient C(n,k) = n!/(k!(n-k)!) counts the number of k-element subsets that can be chosen from a set of n elements, provable either by a direct combinatorial argument or by counting bijections between subsets and orderings.