    # The natural numbers

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.

# Mathematical induction

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 = 02 (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 n2.

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

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

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

(1) P(1), i.e., 6 divides 81 - 21 = 6. This is certainly true. (2) Let’s assume that P(n) is true. 8n+1 - 2n+1 = 8·8n - 2·2n = 6·8n + 2·8n - 2·2n = 6·8n + 2·(8n - 2n). Therefore, 6 divides 8n - 2n -P(n) holds. Inductive case-, and 6 certainly divides 6·8n, 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]

# 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 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 nCk, 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}$ = xn+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}$ + yn+1

We set k as l - 1,

= xn+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}$ + yn+1 = [relabelling k as l] xn+1 + $\sum_{k=1}^{n}${$\binom{n}{k-1}+\binom{n}{k}$}$x^{k}y^{n+1-k}$ + yn+1 = [Pascal’s Triangle] xn+1 + $\sum_{k=1}^{n}\binom{n+1}{k}x^{k}y^{n+1-k}$ + yn+1 = $\sum_{k=0}^{n+1}\binom{n+1}{k}x^{k}y^{n+1-k}$

# Bibliography:

1. Math Typesettings in Hugo, mertbakirc
2. Oxford Mathematics
Bitcoin donation 