Proofs Flashcards
The inite sequence {Fn}, n ∈ Z, n ≥ 0, defined recursively by F0 = 1, F1 = 1, and Fn = Fn−1 +Fn−2 for n ≥ 2
is called the
Fibonacci sequence.
A predicate P(n) defined for n ∈ Z+ is proven true for all integers n ≥ n0 using the Principle of Strong
Mathematical Induction by doing the following:
- Prove P(n0) is true.
- Assume there exists some integer k ≥ n0 such that P(j) is true for every integer j such that n0 ≤ j ≤ k.
- Demonstrate explicitly that P(k + 1) is true.
- Conclude that P(n) is true for all integers n ≥ n0.
Let x, y ∈ R and n ∈ Z+. Then,
(x + y)^n = the sum of n
i=0 (n,i)
x^(n−i) y^i
.
The Binomial Theorem
Every nonempty subset of positive integers has a least element.
Well-Ordering Principle.
Let a, b ∈ Z with b > 0. Then there exist unique integers q and r, with
0 ≤ r < b such that a = bq + r.
Quotient-Remainder Theorem
Let a, b ∈ Z, at least one of which is nonzero. An integer d is called a _______ of a and b if d|a and
d|b.
common divisor
A common divisior d or a and b is called the____ of a and b if d ≥ c for any other
common divisor c of a and b.
Greatest common divisors
If gcd(a, b) = 1, then a and b are
Relatively prime
Let a, b ∈ Z, at least one of which is nonzero. If d = gcd(a, b), then there exist x, y ∈ Z so
that d = ax + by
Theorem 4.24.
Two integers a and b, with at least one nonzero, satisfy gcd(a, b) = 1 if and only if there
exist x, y ∈ Z so that ax + by = 1.
Corollary 4.25
If p is prime and p|ab for a, b ∈ Z, then p|a or p|b.
Euclid’s Lemma
Every positive integer greater than 1 has a unique canonical form
prime factorization.
Fundamental Theorem of Arithmetic
Let A and B be sets. A ____ R from A to B is a subset of A × B. We say a ∈ A is related to b ∈ B if
(a, b) ∈ R.
Relation
Let R be a relation from A to B. The____ of R is (. )(R) = {a ∈ A|(a, b) ∈ R for some b ∈ B}. The ____ of R is Dom(R) = of R is Ran(R) = {b ∈ B|(a, b) ∈ R for some a ∈ A}
Domain, Range
Let R be a relation from A to B. The_____to R, denoted by R−1, is the relation from B to A
defined by (b, a) ∈ R−1 if and only if (a, b) ∈ R.
inverse relation
A relation R defined on a set A called an equivalence relation if and only if it satisfies all three of the
following properties:
- R is reflexive: for every a ∈ A, (a, a) ∈ R.
- R is symmetric: for every a, b ∈ A, if (a, b) ∈ R, then (b, a) ∈ R.
- R is transitive: for every a, b, c ∈ A, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
Let R be an equivalence relation defined on a set A. Then, for a ∈ A, the equivalence class of a determined
by R is the set___
[a] = {x ∈ A|(a, x) ∈ R}
The set of equivalence classes of an equivalence relation R on a nonempty set A partitions A.
Theorem 5.16
For m ∈ Z+, we say that a, b ∈ Z are
denoted a ≡m b (or a ≡ b mod m), if m|(a − b)
Theorem 5.29. Suppose a, b, m ∈ Z with m > 0. The following statements are equivalent:
- a ≡m b.
- a and b have the same remainder when divided by m.
- a = b + km for some k ∈ Z.
For any m ∈ Z+, the relation ≡m is an equivalence relation on Z.
Corollary 5.31
Theorem 5.34. Let m ∈ Z+, and assume ai ≡m bi for i = 1, 2. Then,
- a1 + a2 ≡m b1 + b2
- a1a2 ≡m b1b2, and 3. an1 ≡ mbn1 for all n ∈ Z, n ≥ 2
A _____from a set X to a set Y is a relation from X to Y so that for every x ∈ X, there exists a unique
y ∈ Y such that (x, y) ∈ f.
Function f
The set X is called the
domain of f
