What is a function?
A function f from a nonempty set A to a nonempty set B is an assignment of each element of A to exactly one element of B.
What is function equality?
Two functions are equal iff they have the same domain, the same codomain and map element of the domain to the same element of the codomain.
What is an injective function?
A function f is 1:1 or injective if and only if f(a) = f(b) implies that a=b for all a and b in the domain of f.
Every element in the domain must map to a different element in the codomain.
What is a surjective function?
A function f from A to B is called onto or surjective if and only if for every element b∈B there is an element in a∈A with f(a)=b.
Every element in the codomain must be mapped to from some element in the domain.
What is a bijective function?
A function f is a 1:1 corresponence or a bijection, if it is both surjective and injective - each element in the domain maps to a different element in the codomain and all elements in the codomain must be mapped to.
Suppose f: A→B. How do you show f is injective?
Assume f(x) = f(y) and show x=y
Suppose f: A→B. How do you show f is not injective?
Find x,y ∈ A such that x≠y and f(x) = f(y)
Suppose f: A→B. How do you show f is surjective?
Consider an arbitrary element y∈B and find an element x∈A such that f(x) = y
Suppose f: A→B. How do you show f is not surjective?
Find y∈B such that f(x)≠y for all x∈A.
What is the other way of writing f◦g(x)?
f(g(x))
Is f: N→N, with f(x) = x² injective, surjective, bijective, or none?
Injective
What is a sequence?
A function from a subset of the integers to a set S.
What does aₙ denote?
Used instead of a(n) to denote the nth element. It is a term of the sequence
What is the formula for a geometric sequence?
arⁿ⁻¹
What is the formula for an arithmetic sequence?
a + (n-1)d
What is a recurrence relation for the sequence {aₙ}?
An equation that expresses aₙ in terms of one or more of the previous terms of the sequence
What does it mean if you are asked to solve a recurrence relation?
Find a formula for the nth term of the sequence generated by the recurrence relation. The formula is called the closed formula
What is the index of a summation?
The variable j where j=m underneath the summation sign
When doing proof by induction with summations, after you have assumed the inital statement, what do you do next?
On the top of the summation change k to k+1, then write that this equals the initial summation with k on the top, but add (k+1) to the whole thing and simplify
What is the first step in a geometric proof?
After the initial Sₙ = … statement, write “Then rSₙ =” with an r in front of the initial statement.
