Week 3: Sequence and Summations Flashcards
sequences
- a function from a subset of the integers
- usually set {0, 1, 2..} or {1, 2, 3…} to a set S
notation an (n is subscript)
- denotes the image of the integer n
- an is called a term of the sequence
- an is equal to f(n), where f is a function from {0, 1, 2…..} to S
finite sequence
a sequence that has an end
infinite sequence
a sequence that goes on to the nth degree
geometric progression
- the sequence of the form: a, ar, ar^2, ar^n….. where the initial term a and common ration r are real numbers
- sum of terms: (r^n - 1) / r- 1 when n is not 1
- ex. an = (1/2) ^n
arithmetic progression
- a sequence of the form a, a+d, a+2d, … a+dn
- where the initial term a and the common difference d are real numbers
- sum is n/2[2a + (n-1)d]
recurrence relation
- for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence
- ex. an = a(n-1) + 3
initial conditions of a sequence
- specify the terms for a sequence that preceded the first term where the recurrence relation takes effect
- ex. a0 = 5
sequence is a solution of a recurrence relation if..
-its terms satisfy the recurrence relation
- ex. an = a(n-1) + 3, a0=5, has solution {5, 8, 11, 14….}
fibonacci numbers
- sequence that appears in lots of things, sun of previous two terms
- ex. 1, 1, 2, 3, 45, 8, 13, 21, 34…
definition of the Fibonacci sequence
- initial condition: f0=0, f1=1
- recurrence relation: fn = f(n-1) + f(n-2)
forward substitution method
- start with the first term and increment up until you get the desired answer
- ex. relation an = a(n-1) + 3 fro n=2,3,4…
backward substitution method
- start with the last term and work backwards, substituting calculated values to find the sum of the entire series
index of a summation
- for k = m Σ n (ak) = am + am+1 + ..an
- the variable k is the index of the summation
upper limit
- for k = m Σ n (ak) = am + am+1 + ..an
- the index takes on all the integer values ending at upper limit end (n)
lower limit
- for k = m Σ n (ak) = am + am+1 + ..an
- the index takes on all the integer values start wit the Lower limit m
important sums in CS
see list, MAKE physical flashcards
manipulation of summations
see list, MAKE physical flashcards
geometric series
i = 0 Σ n-1 (r^i) = (r^n - 1) / r-1 (for r is not equal to 1)
product notation
- k=m π n (ak) = am * a(m+1) * .. an
- ex. k=1 π 5 (s^k) = 2^15
closed form solution
- the closed form solution does not involve any terms of the sequence ak
- ex. an = 1 / (2^n)
product notation
n
π a_k
k=m
= a_m × a_m+1×…×a_n
-starts at k=m and takes multiplies each term up to n
