Quiz 2 Flashcards
(13 cards)
Closed Formula Definition
A closed formula for a sequence (a_n) is a formula for a_n in terms of n
Recursive Formula
A recursive formula for (a_n) has two parts:
- A recurrence relation which relates a_n to previous term(s) in the sequence
- initial conditions, which gives the values for the first few terms of the sequences for the recurrence relation to be useful
Square Numbers
The sequence (s_n)_{n >= 1} has closed formula s_n = n^2
Ex) 1, 4, 8, 16, 25, …
Triangular Numbers
The sequence (T_n)_{n >= 1} has closed formula T_n = n(n+1)/2
Ex) 1, 3, 6, 10, 15, 21, …
Powers of 2
The sequence (a_n)_{n >= 0} with closed formula: a_n = 2^n
Ex) 1, 2, 4, 8, 16, 32, …
Fibonacci Numbers
Defined recursively by: F_n = F_{n-1} + F_{n-2} with F_1 = F2 = 1
Geometric Sequences
The ratio between two consecutive terms of the sequence is constant
K-constant sequences
The closed formula for a sequence will be a degree k polynomial if and only if the sequence is k-constant (ie. the kth sequence of differences is constant)
Sequence
Ordered list of numbers
Arithmetic Sequence
the difference between two consecutive terms of the sequence is constant
Telescoping only works if
a. recurrence depends only on previous term, with coefficient 1
b. can find closed formula for partial sum of non-recurrent part
If both a and b are true EXCEPT that the coefficient doesn’t have to be 1, we can use iteration
Characteristic Root Technique
Let x, y be real numbers. A recurrence relation of the form: a_n = x(a_n-1) + y(a_n-2)
is satisfied by the sequence 1, t, t^2, t^3, … (t =/ 0 ) if and only if: t^2 - xt - y = 0
If both 1, r, r^2, r^3, … and 1, q, q^2, q^3, … satisfy this same recurrence relation, then so does: a_n = cr^n + dq^n for any numbers c and d
Closed Formula for the Fibonacci Sequence is
F_n = 1/sqrt(5) (1 + sqrt(5))^n / 2 - 1/sqrt(5) (1-sqrt(5) / 2)^ n
