A natural number is a number that occurs commonly and obviously in nature. As such, it is a whole, non-negative number, that is, a member of the sequence 0, 1, 2, 3, …, obtaining by starting from zero and adding 1 successively. The set of natural number is denoted by Ν. Hence, Ν = {0, 1, 2, 3, …}.

Natural numbers can be added and multiplied, i.e., **if m and n are natural numbers**, then **m + n** and **m x n** (aka m.n or mn) are also **natural** numbers.

**Zero is the additive identity for whole numbers**, i.e., when Zero is added to any given whole number, the resultant number is always equal to the given whole number:
n + 0 = n, ∀ n ∈ ℕ (for all n in the natural numbers).

**One is the multiplicative identity of whole numbers**. If we multiply one to any whole number the result will be the same whole number:
n x 1 = n, ∀ n ∈ ℕ

Natural numbers have **order**, addition, and multiplication.
Definition. Let m and n be natural numbers. We write m ≤ n to **mean or express that
there exists another natural number k such that m + k = n**. More formally,
∀ m, n ∈ ℕ, m ≤ n mean that ∃ k: m + k = n.

**Principle of induction**. It is a way of proving that P(n) is true for all integers n ≥ a. Let P(n) be a family of statements indexed
by the natural numbers. Suppose that:

- (i) P(0) is true. This is the
**Base case**and… - (ii) for any n, if P(n) is
true then P(n + 1) is also true. This is the
**Inductive case.**

Then P(n) is true for all natural numbers n. Proof by induction is analogous to the toppling of dominoes. If dominoes are stacked in such a way (sufficiently close) that if the nth domino falls, it will push the (n + 1)th domino over, then for every domino to fall we only need to topple the first one.

Problem: Prove that for any integer n ≥ 0,
0 + 1 + 2 + 3 + ··· + n = $\sum_{k=0}^n$ k = ^{n(n+1)}⁄_{}2.
Proof. Let P(n) denote the statement that the proposition $\sum_{k=0}^n$ k = ^{n(n+1)}⁄_{}2 holds for that particular n.

(i) P(0) is true because 0 = ^{0 (0 + 1)}⁄_{2} = ^{0}⁄_{2}
(ii) Next, we assume that P(n) holds or is true for n.

Then, $\sum_{k=0}^{n+1}$ k = $\sum_{k=0}^{n}$ k + (n + 1) = ^{n(n+1)}⁄_{}2 + (n + 1) -P(n) holds. Inductive case- = ^{n(n+1)+2(n+1)}⁄_{}2 = ^{(n+1)(n+2)}⁄_{}2, and thus P(n+1) is true, QED.

Problem: Prove that the sum of the first n odd numbers is equal to n^{2}.

(i) P(1), i.e., 1 = 1^{2}. This is certainly true.
(ii) Let’s assume that P(n) is true, i.e., 1 + 3 + 5 + 7 + … + (2n - 1) = n^{2}.

P(n+1) = 1 + 3 + 5 + 7 + … + (2n - 1) + (2n + 1) = n^{2} + (2n + 1) -P(n) holds. Inductive case- = (n + 1)^{2}, and thus P(n+1) is true, QED.

Problem: Prove that 6 divides 8^{n} - 2^{n} for every positive integer n.

(1) P(1), i.e., 6 divides 8^{1} - 2^{1} = 6. This is certainly true.
(2) Let’s assume that P(n) is true.
8^{n+1} - 2^{n+1} = 8·8^{n} - 2·2^{n} = 6·8^{n} + 2·8^{n} - 2·2^{n} = 6·8^{n} + 2·(8^{n} - 2^{n}). Therefore, 6 divides 8^{n} - 2^{n} -P(n) holds. Inductive case-, and 6 certainly divides 6·8^{n}, and thus P(n+1) is true, QED.

**Strong Form of Induction**. Let P(n) be a family of statements indexed by the natural numbers. Suppose that

- (i) P(0) is true and
- (ii) for any n, if P(0), P(1), . . . , P(n) are true then P(n + 1) is also true.

Then P(n) is true for all natural numbers n.

Proof. Let Q(n) be the statement ‘P(k) is true for k = 0, 1, … n.’ (i) Q(0) = P(0) is true. (ii) for any n, if P(0), P(1), . . . , P(n) are true (aka if Q(n) is true), then P(n + 1) is also true, that is, P(0), P(1), . . . , P(n), P(n + 1) are true, and therefore, Q(n + 1) holds. Consequently, Q(n) is true for all n ∈ ℕ. Hence P(n) is true for all n ∈ ℕ.

Proposition. **Every natural number** greater than 1 may be expressed as **a product
of one or more prime numbers**.

Proof. Let P(n) be the statement that n may be expressed as a product of prime numbers.

- (i) P(2) is true, since 2 is itself prime.
- (ii) Let n > 2, n ∈ ℕ, and suppose P(m) holds for all m < n. If n is itself a prime, then P(n) is obviously true. Otherwise, n = s·t for some s, t ∈ ℕ with s, t < n. By our inductive hypothesis, s and t can be expressed as products of primes, and therefore n = s·t can also be expressed as a product of prime numbers. By the strong form of induction, P(n) holds for all natural numbers.

Definition. Let’s define **addition** on ℕ by the following rules,

- (i) m + 0 = m, ∀ m ∈ ℕ
- (ii) m + (n + 1) = (m + n) + 1, ∀ n, m ∈ ℕ

Associativity. The operation of **addition on the set of natural numbers ℕ is associative**, that is, *x + (y + z) = (x + y) + z, ∀ x, y, z ∈ ℕ*

Proof.

- (i) z = 0. Then, LHS = x + (y + 0) = x + y = (x + y) + 0 = RHS, ∀ x, y ∈ ℕ
- (ii) Let’s suppose the proposition is true for z = n, and consider the case z = n + 1. Then, ∀ x, y ∈ ℕ,

LHS = x + (y + (n + 1)) = x + ( (y + n) + 1) [*rule (ii) addition’s definition*] = ( x + (y + n) ) + 1 [*rule (ii) addition’s definition*] = ( (x + y) + n ) + 1 [*inductive hypothesis*] = (x + y) + (n + 1) [*rule (ii) addition’s definition*] = RHS. And therefore, by the induction principle, the expression is true ∀ x, y, and z ∈ ℕ.

Definition. Let’s define **multiplication** on ℕ by the following rules,

- (i) m × 0 = 0, ∀ m ∈ ℕ and
- (ii) m × (n + 1) = (m × n) + m, ∀ n, m ∈ ℕ.

Definition. Let’s define **factorial n! on ℕ** by the following rules,

- (i) 0! = 1
- (ii) (n + 1)! = n! × (n + 1), ∀ n ∈ ℕ

Theorem. **Well-ordering property of the natural numbers**. Every non-empty
subset of ℕ has *a least or minimal element*.

Proof. Suppose that there is a non-empty subset S that does *not* have a least element. Let’s define S* to be the complement of S, that is, the set of natural numbers that are not in S.

Let P(n) be the statement that S* contains n.

- (i) 0 ∉ S, since if it were, then S would obviously have a minimal element, namely zero, and therefore P(0) is true.
- (ii) Let’s suppose P(0),…,P(n) hold. Then, n + 1 ∉ S, because if it were, then it would necessary be the minimum element of S since by the inductive hypothesis all the smaller elements of ℕ are not is S. Therefore, n + 1 ∈ S*, P(n+1) holds.

By the strong induction property, n ∈ S* ∀ n ∈ ℕ, and as consequence S = ∅ (empty), i.e., a contradiction with our initial assumption that S is a non-empty subset.

Commutative. The operation of **addition on the set of natural numbers ℕ is commutative**, that is, *x + y = y + x, ∀ x, y ∈ ℕ*

First, we prove the base cases y = 0, y = 1, i.e., we prove that 0 and 1 commute with everything.

- y = 0,
*x + 0 = x = 0 + x, ∀ x ∈ ℕ* - y = 1. Let P(x) be the statement that x + 1 = 1 + x

(i) x = 0, 0 + 1 = 1 = 1 + 0, and therefore P(0) holds.

(ii) Let’s suppose P(x), that is, x + 1 = 1 + x.

(x + 1) + 1 = (1 + x) + 1 [*inductive hypothesis*] = 1 + (x + 1) [*Associative property*], P(x + 1) holds.

- Next, let’s suppose that
*x + y = y + x*.

x + (y + 1) = (x + y) + 1 [*Associative property*] = (y + x) + 1 [*by the induction hypothesis*] = y + (x + 1) [*Associative property*] = y + (1 + x) [*as shown above, zero and one commute with everything*] = (y + 1) + x [*Associative property*]

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 other words, it is the number of ways of picking k outcomes from n possibilities.

Definition. The **value of the binomial coefficient** for natural numbers n and k is read as “n choose k”, denoted as ^{n}C_{k}, and given by,

$\binom{n}{k} = $ ^{n!}⁄_{k!(n-k)!} for 0 ≤ k ≤ n.

$\binom{n}{k} = $ 0 if k > n.

**Pascal’s triangle is an arrangement of binomial coefficient in triangular form**, in which the nth 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 ≤ k ≤ n. Then, the following formula applies,
$\binom{n}{k-1}$ + $\binom{n}{k}$ = $\binom{n+1}{k}$

Proof:
$\binom{n}{k-1}$ + $\binom{n}{k}$ = ^{n!}⁄_{(k-1)!(n-k+1)!} + ^{n!}⁄_{k!(n-k)!} = ^{n!k + n!(n-k+1)}⁄_{k!(n-k+1)!} = ^{n!(k + n -k +1)}⁄_{k!(n-k+1)!} = ^{(n + 1)!}⁄_{k!(n+1-k)!} = $\binom{n+1}{k}$

**Binomial Theorem**. It **describes the algebraic expansion of powers of a binomial**. Let x and y be real numbers, and n be any natural number, it states that the nth power of the sum of both numbers x and y may be expressed as the sum of n+1 terms of the form,
(x+y)^{n} = $\sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k}$

Proof.
(i) n = 0, (x+y)^{0} = 1, $\sum_{k=0}^{0}\binom{0}{k}x^ky^{-k}$ = 1

(ii) Let’s suppose the expression holds for n.

(x+y)^{(n+1)}=(x+y)(x+y)^{n} = [by the inductive hypothesis] (x+y)($\sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k}$) = $\sum_{k=0}^{n}\binom{n}{k}x^{k+1}y^{n-k}$ + $\sum_{k=0}^{n}\binom{n}{k}x^ky^{n+1-k}$ = x^{n+1} + $\sum_{k=0}^{n-1}\binom{n}{k}x^{k+1}y^{n-k}$ + $\sum_{k=1}^{n}\binom{n}{k}x^ky^{n+1-k}$ + y^{n+1}

We set k as l - 1,

= x^{n+1} + $\sum_{l=1}^{n}\binom{n}{l-1}x^{l}y^{n+1-l}$ + $\sum_{k=1}^{n}\binom{n}{k}x^ky^{n+1-k}$ + y^{n+1} = [relabelling k as l] x^{n+1} + $\sum_{k=1}^{n}${$\binom{n}{k-1}+\binom{n}{k}$}$x^{k}y^{n+1-k}$ + y^{n+1} = [Pascal’s Triangle] x^{n+1} + $\sum_{k=1}^{n}\binom{n+1}{k}x^{k}y^{n+1-k}$ + y^{n+1} = $\sum_{k=0}^{n+1}\binom{n+1}{k}x^{k}y^{n+1-k}$

- Math Typesettings in Hugo, mertbakirc
- Oxford Mathematics