1. Mathematical Rules
Square Root Rules logc (ab ) = b · logc (a)
√a = a1÷b
b
logb (a) = logc (a) ÷ logc (b)
logc (1 ÷ a) = − logc (a)
Fraction Rules logc (c) = c
a b a+b
c + c = c logc (1) = 0
a
c − bc = a−bc
a b a·d c·b Summation Rules
c + d = c·d + c·d = a·d+c·b
c·d k
a b a·d c·b a·d−c·b ∑ f (i)
c − d = c·d − c·d = c·d is the sum of f (i) between j and k
i=j
a
c · bd = a·b
c·d 10 10
a
c ÷ d = ac · db = a·d
b
c·b
∑ 5i = 5 ∑ i2
2
common factor sum
i=1 i=1
n n
Exponent Rules ∑ 10 = 10 ∑ 1 = 10n constant sum
ca · cb = ca+b i=1 i=1
ac · bc = (a · b)c k l k
ca / cb = ca−b
∑ f (i) = ∑ f (i) + ∑ f (i) splitting sum
i=j i=j i=l+1
ac ÷ bc = (a ÷ b)c n n
(ca )b = ca·b ∑ (n − i) = ∑ i reverses sum
c−a = 1 ÷ ca i=0 i=0
n
c0 = 1 ∑i= n(n+1)
is arithmetic series O(n2 )
2
c1 = c i=1
0c = 0 n
q n+1 −1
∑ qi = q−1 is geometric series O(q n )
i=0
Logarithm Rules n n
logc (a · b) = logc (a) + logc (b) ∑ 1
i =∫ 1
x · dx is harmonic series O(log n)
logc (a ÷ b) = logc (a) − logc (b) i=1 1
2. Mathematical Proofs
Writing Proofs
● State the proof techniques used (i.e. loop invariant, induction, etc.)
● Keep a linear flow
● Describe every step clearly in words
● Don’t use complicated notation
● Make sure your assumptions are actually obvious
● Finish your proof
1
, Direct Proof
Proving a statement by using a sequence of manipulations (i.e. p ⇒ q )
Example:
If n is an odd integer then n2 is odd.
We assume that n is odd.
n = 2k + 1
n2 = (2k + 1)2 = (2k)2 + 2 · (2k) + 12 = 2 · (2k 2 + 2k) + 1
2
Thus n2 is odd, since it has the form 2k ′ + 1 with k ′ = (2k + 2k) .
Contraposition Proof
Proving a statement by using its inverse (i.e. p ⇒ q by not q ⇒ not p )
Example:
For integer n , if 3n + 2 is odd then n is odd.
We assume that if n is even, then 3n + 2 is even.
Solve with regular direct proof...
Contradiction Proof
Proving a statement by assuming it’s false (i.e. to prove q assume not q)
Example:
This statement is false by definition of the big-O notation. We will prove that this statement is false by
contradiction. There exists positive constants c and n0 such that 0 ≤ n2 log2 (n) ≤ cn2 for all n ≥ n0
0 ≤ log2 (n) ≤ c , we know that logarithmic functions grow faster than constants. Thus for any positive
value of c and n0 , there will exist such that n ≥ no with log2 (n) > c
We have reached a contradiction and the only conclusion can be that our assumption must be false.
Hence, the statement must be false.
Example Proof
Proving a statement by fulfilling a condition and giving a example (i.e. there is an integer x such
that x < 100 )
Example:
This statement is true by definition of the big-Θ notation. By definition n2 − 5n + 10 = Θ(n2 ) , if there exists
positive constants c1 , c2 and n0 such that 0 ≤ c1 n2 ≤ n2 − 5n + 10 ≤ c2 n2 for all n ≥ n0
2
Square Root Rules logc (ab ) = b · logc (a)
√a = a1÷b
b
logb (a) = logc (a) ÷ logc (b)
logc (1 ÷ a) = − logc (a)
Fraction Rules logc (c) = c
a b a+b
c + c = c logc (1) = 0
a
c − bc = a−bc
a b a·d c·b Summation Rules
c + d = c·d + c·d = a·d+c·b
c·d k
a b a·d c·b a·d−c·b ∑ f (i)
c − d = c·d − c·d = c·d is the sum of f (i) between j and k
i=j
a
c · bd = a·b
c·d 10 10
a
c ÷ d = ac · db = a·d
b
c·b
∑ 5i = 5 ∑ i2
2
common factor sum
i=1 i=1
n n
Exponent Rules ∑ 10 = 10 ∑ 1 = 10n constant sum
ca · cb = ca+b i=1 i=1
ac · bc = (a · b)c k l k
ca / cb = ca−b
∑ f (i) = ∑ f (i) + ∑ f (i) splitting sum
i=j i=j i=l+1
ac ÷ bc = (a ÷ b)c n n
(ca )b = ca·b ∑ (n − i) = ∑ i reverses sum
c−a = 1 ÷ ca i=0 i=0
n
c0 = 1 ∑i= n(n+1)
is arithmetic series O(n2 )
2
c1 = c i=1
0c = 0 n
q n+1 −1
∑ qi = q−1 is geometric series O(q n )
i=0
Logarithm Rules n n
logc (a · b) = logc (a) + logc (b) ∑ 1
i =∫ 1
x · dx is harmonic series O(log n)
logc (a ÷ b) = logc (a) − logc (b) i=1 1
2. Mathematical Proofs
Writing Proofs
● State the proof techniques used (i.e. loop invariant, induction, etc.)
● Keep a linear flow
● Describe every step clearly in words
● Don’t use complicated notation
● Make sure your assumptions are actually obvious
● Finish your proof
1
, Direct Proof
Proving a statement by using a sequence of manipulations (i.e. p ⇒ q )
Example:
If n is an odd integer then n2 is odd.
We assume that n is odd.
n = 2k + 1
n2 = (2k + 1)2 = (2k)2 + 2 · (2k) + 12 = 2 · (2k 2 + 2k) + 1
2
Thus n2 is odd, since it has the form 2k ′ + 1 with k ′ = (2k + 2k) .
Contraposition Proof
Proving a statement by using its inverse (i.e. p ⇒ q by not q ⇒ not p )
Example:
For integer n , if 3n + 2 is odd then n is odd.
We assume that if n is even, then 3n + 2 is even.
Solve with regular direct proof...
Contradiction Proof
Proving a statement by assuming it’s false (i.e. to prove q assume not q)
Example:
This statement is false by definition of the big-O notation. We will prove that this statement is false by
contradiction. There exists positive constants c and n0 such that 0 ≤ n2 log2 (n) ≤ cn2 for all n ≥ n0
0 ≤ log2 (n) ≤ c , we know that logarithmic functions grow faster than constants. Thus for any positive
value of c and n0 , there will exist such that n ≥ no with log2 (n) > c
We have reached a contradiction and the only conclusion can be that our assumption must be false.
Hence, the statement must be false.
Example Proof
Proving a statement by fulfilling a condition and giving a example (i.e. there is an integer x such
that x < 100 )
Example:
This statement is true by definition of the big-Θ notation. By definition n2 − 5n + 10 = Θ(n2 ) , if there exists
positive constants c1 , c2 and n0 such that 0 ≤ c1 n2 ≤ n2 − 5n + 10 ≤ c2 n2 for all n ≥ n0
2
