Mathematical Statements and Proofs Lecture 3 (Handout)

MOE Advanced Level Higher 3 (H3) Math Mathematical Proofs and Reasoning Lecture 3 1 / 39

Telegram Chat https://t.me/+My2fLlPuAUxlYjY1 2 / 39

Content 1 Principle of Mathematical Induction and Its Variations 2 Sequence and Series 3 Limits 3 / 39

Definition of Sequences Definition A (real) sequence is a list of numbers in definite order: a1, a2, a3, . . . , an, . . . . . . The number an is called the nth term of the sequence. Example 1 https://en.wikipedia.org/wiki/List_of_integer_sequences 2 https://oeis.org/ 4 / 39

Examples 1 a1 = 2, a2 = 3, a3 = 5, a4 = 7, a5 = 11, ... List of positive prime numbers. There is no known formula to generate the n-th term. 2 a1 = 2, a2 = 4, a3 = 8, a4 = 16, a5 = 32, ... an = 2n are the powers of 2. 3 a1 = 1, a2 = 3, a3 = 7, a4 = 15, a5 = 31, a6 = 63, a7 = 127, ... an = 2n − 1 are the Mersenne numbers. 4 a1 = 1, a2 = 2, a3 = 6, a4 = 24, a5 = 120, ... an = n!. 5 / 39

Fibonacci Sequence The Fibonacci sequence is defined as such. Let a0 = 0, a1 = 1, and an+1 = an + an−1, n ≥ 1. Let’s write out a few more terms. a2 = 1, a 3 = 2, a 4 = 3, a 5 = 5, a 6 = 8, a 7 = 13, ...... The general term is given by the formula an = 1√ 5 " 1 + √ 5 2 !n − 1 − √ 5 2 !n# n ≥ 1. The derivations are omitted. 6 / 39

Golden Ratio The number ϕ = 1 + √ 5 2 is known as the golden ratio . See https://en.wikipedia.org/wiki/Golden_ratio. It is one of the roots of the polynomial x2 − x − 1 = 0. It is an irrational number. Frequently appear in geometry and architecture. Believed to define beauty. It is the limit of the ratio of the Fibonacci sequence, lim n→∞ an+1 an = ϕ. 7 / 39

Observation Observe that a0 = 0< 1 = 20, a 1 = 1< 21, a 2 = 1< 4 = 22, a 3 = 2< 8 = 23, a 4 = 3< 16 = 24. It seems like the difference between an and 2n is larger as n gets larger. So, we might guess (correctly) that for all n ≥ 0, an < 2n. But there are infinitely many n to check, it is not possible to check them all. Moreover, an is obtained from the lower terms. If the lower terms satisfy the inequality, we might be able to use them to show that an satisfies the inequality too. 8 / 39

Mathematical Induction The Principle of Mathematical Induction can be used to prove statements of the form ∀n ∈ Z+, P(n) is true. 1 First prove the base case: P (1) is true. 2 Inductive step: Prove that P (k) ⇒ P (k + 1)is true. We can then conclude that P (n) is true for all n ∈ Z+. P (1) ⇒ P (2) ⇒ P (3) ⇒ · · · · · · ⇒P (k) ⇒ P (k + 1)⇒ · · ·. 9 / 39

Example Prove that nX i=1 1 i(i + 1)= n n + 1, ∀n = 1, 2, 3, ... P (1): 1X i=1 1 i(i + 1)= 1 1 + 1= 1 2 , 1 1 + 1= 1 2 . So, P (1) is true. Suppose P (k) is true. Show that P (k + 1)is true, that is k+1X i=1 1 i(i + 1)= k + 1 k + 2 k+1X i=1 1 i(i + 1) = kX i=1 1 i(i + 1)+ 1 (k + 1)(k + 2)= k k + 1+ 1 (k + 1)(k + 2) by induction hypothesis = k(k + 2) (k + 1)(k + 2)+ 1 (k + 1)(k + 2)= k2 + 2k + 1 (k + 1)(k + 2)= (k + 1)2 (k + 1)(k + 2)= k + 1 k + 2 This proves P (k) ⇒ P (k + 1), and hence P (n) is true for all n ≥ 1. 10 / 39