Math review
Exponents
-
XAXB = XA+B
-
XA / XB = XA-B
-
(XA)B = XAB
-
XN + XN = 2XN (which is not
equal to X2N )
- 2N + 2N = 2N+1
- Why? Can you derive this? (Hint: Use the previous item)
Logarithms
Definition: XA = B if and only if logXB = A
Logarithms used in this course will be to the base 2, unless
otherwise specified
Theorem 1.1 (base change)
logA B = ( logC B ) / ( logC A )
for A,B,C > 0, A != 1
Can you prove this? (Hint: Use definition of log to derive this
property)
Other easlily derived (and provable) properties
These can be shown for any base. Assume base 2, unless otherwise
specified
-
log AB = log A + log B; for A,B > 0
-
log A/B = log A - log B
-
log (AB) = B log A
-
log X < X for all X > 0
-
log2 1 = 0
-
log2 2 = 1
-
log2 1024 = 10
-
log2 1048576 = 20
Proof Techniques
Common proof techniques that will be used in data structure and
algorithm analysis (and in CS, in general):
- Proof by induction
- Proof by contradiction
- Proof by counter-example
- This one is typically used for showing that an assertion is
false
- Informally, your professors are sometimes allowed to use
Proof-by-I-told-you-so! ;-)
Proof by Induction
Given a statement or theorem to prove:
- Establish a base case. i.e. show the theorem is true for
some
small
value(s), usually a trivial step to prove
- Assume an inductive hypothesis.
- e.g. Assume the theorem is true for all cases up to some limit
k
- Using this assumption, show that the theorem holds for the next
value k+1
- Note that in doing this, we are showing that "it's true for 1 ... k"
implies that "it's true for k+1"
Proof by contradiction
To use this technique to prove a statement or theorem:
- Assume that the theorem is false
- From this assumption, show how it implies that some known
(i.e. axiomatic) property is false
- Since this would lead to a contradiction, the original assumption
must be erroneous, so the theorem is true
Proof by counterexample
This is the easiest way to prove a given assertion to be
false.
- For a statement to be true, it must be true in all cases
- Provide one counterexample. This will show that in at least one
case, the assertion does not hold (therefore, it's false)
Example 1 (induction)
Suppose we use the following definition of the Fibonnaci series:
-
F0 = 1 , F1 = 1
Fi = Fi-1 + Fi-2 , for i > 1
Prove the following (by induction):
-
Fi < (5/3)i for all i >= 1
(Solution in class)
Example 2 (counter-example)
Using the same Fibonnaci definition above, is this statement true or
false?
All we need is one counterexample to show the formula is false. (To be
true, it must hold for all values of k).
- F11 = 144.
But 112 = 121.
144 > 121
Example 3 (contradiction)
Theorem: There are an infinite number of primes
Proof:
- Suppose the theorem is false. Then there are a finite number of
primes
- Therefore, you can list them. Let the primes be P1,
P2, ... , Pk be the finite list of primes, from
smallest to largest. (i.e. Pk is the largest prime)
- Consider N =
P1P2P3...Pk
+ 1
- Clearly, N is larger than Pk (which is the largest
prime), so N must not be prime
- However, none of the primes in the list divides N exactly, because
the remainder is always 1
- This contradicts the known property that every number is either
prime or a product of primes
- Therefore the assumption (finite primes) is false, implying the
theorem is true