Introduction • Sequences are ordered lists of elements. ○ 1,2,3,5,8 ○ 1,3,9,27,81,… • Sequences arise throughout mathematics, computer science, and in many other disciplines, ranging from botany to music. • We will introduce the terminology to represent sequences and sums of the terms in the sequences. Sequences • Definition ○ A sequence is a function from a subset of the integers to a set S. ○ The notation a_n is used to denote the image of the integer n. ○ We can think of a_n as the equivalent of f(n) ○ where f is a function from {0,1,2,…..} to S. ○ We call a_n a term of the sequence. • Example ○ Consider the sequence {a_n } where ○ a_n=1/n, {a_n }={a_1,a_2,a_3,…} ○ 1, 1/2,1/3,… Strings • A string is a finite sequence of characters from a finite set (an alphabet). • Sequences of characters or bits are important in computer science. • The empty string is represented by λ. • The string abcde has length 5. Geometric Progression • Definition ○ A geometric progression is a sequence of the form: a,ar,ar2,…,arn,… ○ where the initial term a and the common ratio r are real numbers • Example 1 ○ Let a = 1 and r = −1. Then: ○ {b_n }={b_0,b_1,b_2,b_3,b_4,…}={1,−1,1,−1,1,…} • Example 2 ○ Let a = 2 and r = 5. Then: ○ {c_n }={c_0,c_1,c_2,c_3,c_4,…}={2,10,50,250,1250,…} • Example 3 ○ Let a = 6 and r=1/3. Then: ○ {d_n }={d_0,d_1,d_2,d_3,d_4,…}={6,2, 2/3,2/9,2/27,…} Arithmetic Progression • Definition ○ A arithmetic progression is a sequence of the form ○ a,a+d,a+2d,…,a+nd,… ○ where the initial term a and the common difference d are real numbers • Example 1 ○ Let a = −1 and d = 4: ○ {s_n }={s_0,s_1,s_2,s_3,s_4…}={−1,3,7,11,15…} • Example 2 ○ Let a = 7 and d = −3: ○ {t_n }={t_0,t_1,t_2,t_3,t_4…}={7,4,1,−2,−5…} • Example 3 ○ Let a = 1 and d = 2: ○ {u_n }={u_0,u_1,u_2,u_3,u_4…}={1,3,5,7,9…} Recurrence Relations • A recurrence relation for the sequence {a_n} is an equation that ○ expresses a_n in terms of a_0, a_1, …, a_(n−1) ○ for all integers n with n≥n_0, where n_0 is a nonnegative integer. • A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. • The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect. • Example ○ Let {a_n} be a sequence that satisfies § the recurrence relation a_n=a_(n−1)+3 for n=1,2,3,4 § and suppose that a_0=2. ○ What are a_1, a_2 and a_3? ○ a_1=a_0+3=2+3=5 ○ a_2=5+3=8 ○ a_3=8+3=11 Fibonacci Sequence • Define the Fibonacci sequence, f0 ,f1 ,f2,…, by: ○ Initial Conditions: f_0=0, f_1=1 ○ Recurrence Relation: f_n=f_(n−1)+f_(n−2) • Find f_2,f_3,f_4,f_5,f_6 ○ f_2=f_1+f_0=1+0=1 ○ f_3=f_2+f_1=1+1=2 ○ f_4=f_3+f_2=2+1=3 ○ f_5=f_4+f_3=3+2=5 ○ f_6=f_5+f_4=5+3=8 Solving Recurrence Relations • Finding a formula for the n-th term of the sequence generated by a recurrence relation is called solving the recurrence relation. • Such a formula is called a closed formula. • Various methods for solving recurrence relations will be covered in Chapter 8 where recurrence relations will be studied in greater depth. • Here we illustrate by example the method of iteration in which we need to guess the formula. The guess can be proved correct by the method of induction (Chapter 5). • Method 1: Working upward, forward substitution ○ Let {a_n} be a sequence that satisfies the recurrence relation ○ a_n=a_(n−1)+3 for n = 2,3,4,… and suppose that a_1=2 ○ a_2=2+3 ○ a_3=(2+3)+3=2+3∙2 ○ a_4=(2+2∙3)+3=2+3∙3 ○ ⋮ ○ a_n=a_(n−1)+3=(2+3∙(n–2))+3=2+3(n–1) • Method 2: Working downward, backward substitution ○ Let {a_n} be a sequence that satisfies the recurrence relation ○ a_n=a_(n−1)+3 for n = 2,3,4,… and suppose that a_1=2 ○ a_n=a_(n−1)+3 ○ =(a_(n−2)+3)+3=a_(n−2)+3∙2 ○ =(a_(n−3)+3)+3∙2=a_(n−3)+3∙3 ○ =… ○ =a_2+3(n–2)=(a_1+3)+3(n–2)=2+3(n–1) Summations • Sum of the terms a_m,a_(m+1),…,a_n from the sequence {a_n } • Notation for a_m+a_(m+1)+…+a_n ○ ∑_(j=m)^n▒a_j • The variable j is called the index of summation. It runs through all the integers starting with its lower limit m and ending with its upper limit n. • More generally for a set S ○ ∑_(j∈S)▒a_j • Examples: ○ r0+r1+r2+r3+…+rn=∑_(j=0)n▒r^j ○ 1+1/2+1/3+1/4+…=∑_(i=1)^∞▒1/i ○ If S={2,5,7,10} then ∑_(j∈S)▒a_j =a_2+a_5+a_7+a_10 Geometric Series • Sums of terms of geometric progressions • Product Notation • Sum of the terms a_m,a_(m+1),…,a_n from the sequence {a_n } • Notation for a_m×a_(m+1)×…×a_n ○ ∏_(j=m)^n▒a_j
