There is nothing more practical than a good theory, Leonid Brezhnev.
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, …, 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 whole number, the resultant number is the given whole number itself: n + 0 = n, ∀n ∈ ℕ (meaning for all n numbers 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 two arbitrary natural numbers. We write m ≤ n to mean or express that there exists another natural number k such that m + k = n. Sometimes, this is written more concisely as ∀m, n ∈ ℕ, m ≤ n ⇒ ∃k ∈ ℕ: m + k = n.
It satisfies three properties: reflexive (n ≤ n), antisymmetric (if n ≤ m and m ≤ n, then n = m), and transitive (if n ≤ l, l ≤ m, then n ≤ m).
Proof (transitive)
Let’s assume that n ≤ l, l ≤ m ⇒ ∃k, k’∈ ℕ such that l = n + k, m = l + k’ ⇒ m = (n + k) + k’ = [By Associativity] n + (k + k’) ⇒ ∃ (k + k’) = k’’∈ ℕ: m = n + k’’ ⇒ n ≤ m∎
Given the set ℕ of natural number and the successor map or function s: ℕ → ℕ, sending each natural number to the next one, the natural numbers could be defined recursively as follows, 0 = {} = ∅, 1 = {1}, 2 = {0, 1},... where the successor function is s(n) = n ∪ {n} and satisfies,
Definition. Let’s define addition on ℕ using the following axioms or rules, (recursive definition, rd for short)
(i) m + 0 = m, ∀ m ∈ ℕ
(ii) m + s(n) = s(m + n), ∀ n, m ∈ ℕ
Let’s denote s(n) = n + 1, the axioms above can be rewritten more concisely as:
(i) m + 0 = m, ∀ m ∈ ℕ
(ii) m + (n + 1) = (m + n) + 1, ∀ n, m ∈ ℕ
Mathematical induction can be also expressed in a more conventional fashion. Let P(n) be a property for natural numbers.
(i) Base case: If P(0) is true.
(ii) Induction step: ∀n ∈ ℕ: P(n) is true ⇒ P(n + 1) is also true.
Then, P(n) is true ∀n ∈ ℕ.
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.
P(n): ∀x, y ∈ ℕ: x + (y + n) = (x + y) + n
LHS = 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] (x + y) + (n + 1) = RHS. And therefore, by the induction principle, the expression is true ∀ x, y, and n ∈ ℕ.
Definition. Multiplication is a map or function, · (or “x”): ℕ → ℕ. It can be defined recursively on ℕ by the following rules,
(i) 0 · m = 0, ∀ m ∈ ℕ
(ii) (n + 1) · m = (n · m) + m, ∀ n, m ∈ ℕ.
The multiplication has the following properties: (∀ n, m ∈ ℕ)
Proof by induction (Distributive law)
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 the natural numbers has a least or minimal element.
The set of natural number ℕ is well-ordered. On the contrary, ℤ, ℚ, and ℝ are ordered set, but are not well-ordered since minimal elements need not exist in their subsets.
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.
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.
For the sake of contradiction, let’s suppose the equation is false. Let S be the set of all counterexamples to this equation ⇒ [Well-Ordering Principle] there is a minimal element k in S: 1 + 3 + 5 + … + (2k -1) ≠ k^{2}, and k ≠ 1 (we know that the equation holds for k = 1, 1^{2} = 1)) ⇒ [k is a minimal element in S] the equation holds for k-1: 1 + 3 + 5 + … + (2(k-1) -1) = (k-1)^{2} ⇒ [Let’s add (2k -1) to both sides of the equation] 1 + 3 + 5 + … + (2k -3) + (2k -1) = (2k -1) + (k-1)^{2} = 2k -1 + k^{2}+1 -2k = k^{2} ⊥ (k ∈ S^{*})
First, we prove the base cases y = 0, y = 1, i.e., we prove that 0 and 1 commute with everything.
(i) n = 0, 0 + 1 = 1 = 1 + 0, and therefore P(0) holds.
(ii) Let’s suppose P(n) is true, that is, n + 1 = 1 + n.
(n + 1) + 1 = [inductive hypothesis] (1 + n) + 1 = [Associative property] 1 + (n + 1), P(n + 1) holds.
x + (y + 1) = [Associative property] (x + y) + 1 = [By the induction hypothesis] (y + x) + 1 = [Associative property] y + (x + 1) = [As it has been shown above, the natural numbers zero and one commute with everything] y + (1 + x) = [Associative property] (y + 1) + x ∎
To sum up, the addition of natural numbers + is a map or function, +: ℕ x ℕ → ℕ with the following properties: ∀m, n, k ∈ ℕ,
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.
Permutation with Repetition. A permutation is an arrangement of objects in a particular way or order. Example: Permutations to a three-digit lock is n^{k} = 10^{3} where n is the number of things to choose from, and we pick or select k of them, repetition is allowed and order matters.
Permutation without Repetition. Example: We have 8 people (say Alice, Bob, Charles, ···, H). How many ways can we award a 1st, 2nd, and 3rd place prize among eight contestant? Sol: 8 (8 choices for gold metal) x 7 (7 choices for silver medal) x 6 (bronze). Another way of thinking about it is this: G (gold) S (Silver) B (bronze) NS ··· NS (There are 5 Non selected). If we have n items or elements and want to select k in a certain order, the solution is P(n, k) = $\frac{n!}{(n-k!)} = \frac{8!}{(8-3)!}$ No repetitions, order matters. We remove (8-3)! because we are only interested in the first three selections (G, S, B) and get rid of everyone else (NS ···_{5} NS). The order of losers is completely irrelevant, that is, Alice Bob Charlie NS_{1} NS_{2} ··· NS_{5} = Alice Bob Charlie NS_{2} NS_{1} ··· NS_{5} = ···
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 I 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 ^{n}C_{k}, C(n, k) = $\frac{n!}{(n-k)!k!} = \frac{8!}{(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. 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 is read as “n choose k”, denoted as ^{n}C_{k}, C(n, k) or $\binom{n}{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}$ ∎