JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

The Natural Numbers and induction. The Binomial Theorem.

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:

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. Mathematical induction

Mathematical induction

 

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

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.

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

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.

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,

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

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.

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.

(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.

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

JustToThePoint Copyright © 2011 - 2023 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.