Report

Discrete Mathematics and Applications Chapter 5: Sequences, Mathematical Induction and Recursion 5.1 Sequences Yan Zhang ([email protected]) Department of Computer Science and Engineering, USF Sequences • A sequence is a function. • Function ∶ → – Every element in is mapped to only one element in , such that (, ) ∈ . Domain: A ∶ → Codomain: B Not allowed 2 Sequences Definition • A sequence is a function. • Domain is either all the integers between two given integers or all the integers greater than or equal to a given integer. Finite sequences: , +1 , +2 , ⋯ , Domain +1 +2 ⋯ Codomain +1 +2 ⋯ Infinite sequences: , +1 , +2 , ⋯ Domain +1 +2 ⋯ Codomain +1 +2 ⋯ (read “ sub ”) is called a term. in is called a subscript or index. Initial term: Final term: 3 Sequence Example 1 Finding Terms of Sequences Given by Explicit Formulas Define sequences 1, 2, 3, … and 2, 3, 4, … by the following explicit formulas: Compute the first five terms of both sequences. Solution: 1 = 2 = 1 1+1 2−1 2 1 2 1 , 2 2 2 = , 2+1 3 3−1 2 = , 3 3 3 3 = , 3+1 4 4−1 3 = , 4 4 = , 2 = 3 = 4 = = 4 = 5 = 3 = 4 4 = , 4+1 5 5−1 4 = , 5 5 5 = 6 = 5 5 = 5+1 6 6−1 5 = 6 6 Note: all terms of both sequences are identical. 4 Sequence Example 2 Finding an Explicit Formulas to Fit Given Initial Terms Find an explicit formula for a sequence that has the following initial terms: 1 1 1 1 1 1, − , , − , , − , ⋯ 4 9 16 25 36 Solution: • Denote the general term of the sequence by and suppose the first term is 1 . 1 = 1 , 12 2 = (−1) 1 , 22 3 = 1 , 32 4 = (−1) 1 , 42 5 = 1 , 52 6 = (−1) 1 62 • An explicit formulator that gives the correct first six terms is: 1 +1 = (−1) 2 5 Summation Notation Given a sequence , +1 , +2 , ⋯ , , Domain +1 +2 ⋯ Codomain +1 +2 ⋯ The summation from equals to of -sub-: = = + +1 + ⋯ + Summation notation Expanded form : the index of the summation : the lower limit of the summation : the upper limit of the summation 6 Summation Example – Computing Summations Let 1 = −2, 2 = −1, 3 = 0, 4 = 1, and 5 = 2. Compute the following: a. 5 =1 5 = 1 + 2 + 3 + 4 + 5 = −2 + −1 + 0 + 1 + 2 = 0 =1 b. c. 2 =2 2 =2 = 2 = −1 2 =1 2 2 =1 2 = 2 + 4 = −1 + 1 = 0 7 Summation Example – Changing from Summation Notation to Expanded Form Write the following summation in expanded form: Solution: 8 Summation Example – Changing from Expanded Form to Summation Notation Express the following using summation notation: Solution: The general term of this summation can be expressed as for integers k from 0 to n. Hence 9 Summation Notation - Recursive Definition If is any integer and < , then = = +1 = + +1 = = +2 +1 = = + +2 = ⋯ −1 = = + = Recursive definition is useful to rewrite a summation, – by separating off the final term of a summation – by adding a final term to a summation. 10 Recursive Definition Example – Separating Off a Final Term and Adding On a Final Term a. Rewrite b. Write by separating off the final term. as a single summation. Solution: a. b. 11 Summation Notation - A Telescoping Sum • In certain sums each term is a difference of two quantities. For example: = 1 1 − , +1 = , ⋯ , • When you write such sums in expanded form, you sometimes see that all the terms cancel except the first and the last. + +1 + +2 1 1 1 1 1 1 = − + − + − +1 +1 +2 +2 +3 • Successive cancellation of terms collapses the sum like a telescope. 12 A Telescoping Sum Example Some sums can be transformed into telescoping sums, which then can be rewritten as a simple expression. For instance, observe that Use this identity to find a simple expression for 13 Product Notation Given a sequence , +1 , +2 , ⋯ , , Domain +1 +2 ⋯ Codomain +1 +2 ⋯ The product from equals to of -sub-: = = ∙ +1 ∙ ⋯ ∙ A recursive definition for the product notation is the following: If is any integer, then 14 Product Notation Example – Computing Products Compute the following products: a. b. Solution: a. b. 15 Properties of Summations and Products 16 Properties of Summation & Product Exercise Let = + 1 and = − 1 for all integers . Write each of the following expressions as a single summation or product: a. b. 17 Properties of Summation & Product Exercise Solution: a. 18 Properties of Summation & Product Exercise Solution: b. 19 Change of Variable • The index symbol in a summation or product is internal to summation or product. • The index symbol can be replaced by any other symbol as long as the replacement is made in each location where the symbol occurs. = = = and = = = • As a consequence, the index of a summation or a product is called a dummy variable. • A dummy variable is a symbol that derives its entire meaning from its local context. Outside of that context, the symbol may have another meaning entirely. 20 Change of Variable Exercise 1 summation: change of variable: 21 Change of Variable Exercise 1 - Solution Solution: • First calculate the lower and upper limits of the new summation: Thus the new sum goes from j = 1 to j = 7. • Next calculate the general term of the new summation by replacing each occurrence of k by an expression in j : • Finally, put the steps together to obtain 22 Factorial Notation A recursive definition for factorial is the following: Given any nonnegative integer , 23 Factorials Exercise Simplify the following expressions: a. b. c. d. Solution: a. e. d. e. b. 24 Factorials Exercise Solution c. 25 “n Choose r ” Notation Chose 2 objects from {a,b,c,d}: {a, b}, {a, c}, {a, d}, {b, c}, {b,d}, and {c, d}. 26 “n Choose r” Exercise Use the formula for computing expressions: a. b. to evaluate the following c. Solution: a. 27 “n Choose r” Exercise b. c. 28 n Choose r Properties • • • • • 0 = = = = = for 0 ≤ ≤ − =1 −+1 for > 0 −1 −1 for < − −1 for , > 0 −1 29 Exercise Prove that for all nonnegative integers and with + 1 ≤ , − = . +1 +1 30 Exercise Prove that for all nonnegative integers and with + 1 ≤ , − = . +1 +1 Hint: − − ! = ∙ +1 + 1 ! − ! = − +1 = ! (+1)! −−1 ! ∙ ! ! − ∙ −−1 ! = +1 31