Report

Numbers, Sequences and Sums In this lecture we introduce basic materials that will Frequently be used throughout the course. We will cover the important sets of numbers , the concept of integer sequences, summations and products. Instructor: Hayk Melikyan [email protected] MelikyanElem Numb Theory/Fall05 1 Numbers Integers. The Well-Ordering Property: Every nonempty set of positive integers has a least element Rationals: Irrationals: Theorem: 2 is irrational. Algebraic numbers: A number which is the root of polynomial with integer coefficients. 5, ¾, or 2 •Transcendent numbers: e, π, 3 MelikyanElem Numb Theory/Fall05 2 2 Sequences A sequence {an} is a list of elements a1, a2, a3, . . . A Geometric Progression is a sequence of the form a, ar, ar2, ar3, …ark ,. . . an = 3(7)n , a1 = 21, a2 =147 what about a23 ? Triangular numbers t1, t2, t3, . . . tk, . . . Is the sequence where tk is the number of dots in the triangular array of k rows with j dots in jth row. An Arithmetic Progression is a sequence of the form a, a+d, a+2d, . . . a + (n-1)d, . . . MelikyanElem Numb Theory/Fall05 3 Countable sets A set is called countable if it is finite or there exists a one –to –one correspondence between the set of positive integers and the set. Theorem: The set of rational numbers are countable. Sums and products, notations and properties. MelikyanElem Numb Theory/Fall05 4 Mathematical induction Theorem: A set of positive integers that contains the integer 1, and has the property that, for every positive integer n, if it contains all positive integers 1, 2, 3, …, n, then it also contains the integer n+1, must be the set of all positive integers. Examples: 1. Let Sn denote the sum of the first n natural numbers, that is Sn = 1 + 2 + 3 + … + n. Prove that Sn = n(n+1)/2 First base case: n =1 Second Induction Hypothesis: Example2: Prove that 2n > n for all positive integers MelikyanElem Numb Theory/Fall05 5 Recursive definitions We say that function f(n) is drfined recursivly if The value of f (1) is specified and for each positive integer n the rule is given for coumpiting f(n+1) from f(n). Example: factorial function MelikyanElem Numb Theory/Fall05 6 The Fibonacci Numbers Definition: The Fibonacci sequence is defined recursively by f1 = 1, f2 = 1 and fn = fn-1 + fn – 2 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . What is the sum of first Fibonacci numbers? f1 + f2 + f3 + … + fn = fn+2 - 1 What about the following sum f1 + f3 + f5 + … + f2n -1 = f2n MelikyanElem Numb Theory/Fall05 7 More examples: Let assume that α and β (α > β) and is the root of the following quadratic equation x2 – x -1 =0 Use mathematical induction to verify that fn = (αn - βn)/(α - β) MelikyanElem Numb Theory/Fall05 8 Binomial Coefficients How to compute (x + y)n = (x + y)2 = (x + y)3 = (x + y)4 = MelikyanElem Numb Theory/Fall05 9