Chapter 2 - Mathematics Review
Sets of Numbers
À - Natural numbers {1, 2, 3, 4, …} positive whole numbers, infinite, countable
 - Real numbers (i.e., floating point numbers) infinite, not countable
Integers both non-negative and negative whole numbers {…-2, -1, 0, 1, 2, …}, includes zero, countable
Rational numbers can be expressed as a fraction of two whole numbers (i.e., 0.25 = ¼), countable
is not rational, i.e., can not be expressed as a/b where a and b are whole numbers.
Cardinality
If X is a finite set, |X| is the number of elements in the set.
Polynomial of degree n
Example:
3x3+5x2+4x+x4 Polynomial of degree 4 (a common trick in this course)
Set Notation
[a, b] All the number between a and b, including both a and b.
(a, b) All the number between a and b, excluding both a and b.
Examples:
[3, 6] = {3, 4, 5, 6} assuming a and b are integers. (1, 2) = { } [1, 3) = {1, 2}
[3.0, 6.0] is infinite, assuming a and b are Real Numbers
Sequences are like sets except the order of the elements matter.
Given a = 1, 2, 3 and b = 3, 1, 2, the sequences a and b are not equal.
Sequence a[n] = a0, a1, a2, …, an-1
1, 5, 6, 10, 14, 23 increasing sequence 9, 6, 5, 3, 2 decreasing sequence
1, 2, 2, 6, 7, 7 non-decreasing sequence 9, 9, 9, 5, 4 non-increasing sequence
3, 7, 10 is a sub-sequence of a = 1, 3, 4, 7, 8, 10
Logic
ÙÚ interpreted as ((not p) and q) or (not r) Can also be written as ~pq+~r
~pq is true when p = 0 and q = 1. Also, ~r is true when r = 0.
Thus, ~pq+~r is true when r = 0 or when p = 0 and q = 1.
Permutations - number of different orderings (analogous to sequences).
Given {a,b,c}, there are 3! = 6 permutations (abc, acb, bca, bac, cab, cba).
Combinations - number of different subsets (order does not matter).
Given {a,b,c}, there is one combination of size 3.
Given {a,b,c,d} there are 4 combinations of size 3 (abc, bcd, cda, dac).
Binomial coefficient counts the number of combinations, i.e., the number of k-element subsets of an n-element set.
Logarithms & Exponents
Example 23 = 8, so
Thus, and (Logarithms cancel out exponentials)
(Change of base formula)
Natural Log = ln(x) = logex where e = 2.718
If base not given, assume base equals 2. log(x/y) = log(x) - log(y) log(xy) = log(x) + log(y)
Summations
Proof by Induction
Example
Side A = Side B
Step 1: Show that the base case is true: n = 1 Side A: Side B:
Substitute base value, i.e., n = 1, on both Side A and Side B and show that the numeric value is equal.
Step 2: Assume true for n. This is important because we can use the equality to perform a substitution
Step 3: Prove true for n+1
Side A: Side B:
Try to re-write Side A or Side B so that it includes the initial equality, i.e., Side A:
Notice how Side A is re-written as (n+1) plus the initial equality.
Now, perform the substitution and simplify side A:
Side A:
Now, simplify side B.
Side B: