Mastering Mathematics: Proving Techniques and Exponents Manipulation

Mathematics review and proving techniques Reading: Sections 1.1, 1.2, 1.3

Math review Exponents: o ?,?2= ? ?,?3= ? ? ? ? o ??= ? ? ? o In COP4530, most like you will be dealing with ?,?2,?3 The math in this class is used to count the number of operations in a program. for (i=0; i<N; i++) { A[i] = 0; } for (i=0; i<N; i++) for (k=0; k < N; k ++) { A[i][k] = 0; }

Exponents Manipulating exponents: o????= ?? ??= ?? o??/ ??= ?? o(??)?= ?? o??+ ??= ? o2?+ 2?= ?

Exponents Manipulating exponents: ? ? ?+? o ????= ?? ??= ? ? =??+? ? ? = ? ? ? ? ? ? o ??/ ??= ? ? =?? ? / ? ? = ? ? ? ? ? ? o (??)?= ? ? = ??? ? ? ? ? o ??+ ??= 2?? o 2?+ 2?= 2?+1

Logarithms Definition: XA= B if and only if logXB = A. o Theorem 1.1 (base change): logAB = ( logCB ) / ( logCA ) for A,B,C > 0, A != 1 o In our book log(X) refers to base of 2. In most other literature, this notion is based on 10. For the base of 10, log ? = ???10? For the base of 2, lg ? = ???2(?) o This highlights a fact that the base of a logarithms function usually does not matter (especially for algorithm analysis).

Logarithms Other easlily derived (and provable) properties (all can be proved for any base) olog AB = log A + log B; for A,B > 0 olog A/B = log A - log B olog (AB) = B log A olog X < X for all X > 0

Logarithms Proof: log AB = log A + log B; for A,B > 0 X = log AB 10?= ?? Y = log A 10?= ? Z = log B 10?= ? We need to prove X = Y + Z Since 10?= ?? = 10?10?= 10?+? , X = Y+Z.

Useful logarithms table 101= 10???1010 = 1 102= 100???10100 = 2 103= 1,000???101,000 = 3 104= 10,000???1010,000 = 4 105= 100,000???10100,000 = 5 106= 1,000,000???101,000,000 = 6 107= 10,000,000???1010,000,000 = 7 108= 100,000,000???10100,000,000 = 8 109= 1,000,000,000???101,000,000,000 = 9 1010= 10,000,000,000???1010,000,000,000 = 10 Give an estimation of: ???105,341,254

Useful logarithm table 21= 2 lg(2) = 1 22= 4 lg(4) = 2 23= 8 lg(8) = 3 24= 16 lg(16) = 4 25= 32 lg(32) = 5 26= 64 lg(64) = 6 27= 128 lg(128) = 7 28= 256 lg(256) = 8 29= 512 lg(512) = 9 210= 1024 lg(1024) = 10 211= 2,048 lg(2,048) = 11 212= 4,096 lg(4,096) = 12 213= 8,192 lg(8,192) = 13 214= 16,384 lg(16,384) = 14 215= 32,768 lg(32,768) = 15 216= 65,536 lg(65,536) = 16 217= 131,072 lg(131,072) = 17 218= 262,144 lg(262,144) = 18 219= 524,288 lg(524,288) = 19 220= 1,048,576 lg(1,048,576) = 20 Estimate: lg(333,253) lg(40,000,000,233) 210 1,000,220 1,000,000,230 1,000,000,000,240 1,000,000,000,000

Math review Series: some examples. ? 2?= 20+ 21+ + 2?= 2?+1 1 ?=0 ? ??+1 1 ? 1 ??= ?0+ ?1+ + ??= ?=0 ? ?2 ?(? + 1) 2 ? = 1 + 2 + + ? = 2 ?=1 ? 1 ?= 1 +1 2+1 1 ? ????(?) 3+ + ?=1

Proof Techniques Common proof techniques that will be used in data structure and algorithm analysis (and in CS, in general): oProof by induction oProof by contradiction oProof by counter-example This one is typically used for showing that an assertion is false

Proof by Induction Given a statement or theorem to prove: 1. Establish a base case. i.e. show the theorem is true for a small value, usually a trivial step to prove. 2. Assume an inductive hypothesis. e.g. Assume the theorem is true for all cases up to some limit k 3. 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"

Example (induction) Let us define Fibonnaci series as follows: ?0= 1,?1= 1 ??= ?? 1+ ?? 2 Prove: ??< (5 3)?,??? ? 1 ?2= ?1+ ?0= 1 + 1 = 2 ?3= ?2+ ?1= 2 + 1 = 3 ?4= ?3+ ?2= 3 + 2 = 5

Induction example ??< (5 3)?,??? ? 1 Proof: Base case: when i= 1, ?1= 1 < (5 when i = 2, ?2= 2 < (5 Induction hypothesis: ??< (5 We need to prove the induction case when i = k+1: ??+1 < (5 ??+1= ??+ ?? 1< (5 (5 3)1 3)2 3)?,??? ? 1 and i <= k 3)?+1 3)?+(5 3)? 1= (1 +5 3)(5 3)? 1=24 9(5 3)? 1< 25 9(5 3)? 1=(5 3)2(5 3)? 1 = 3)?+1

Proof by contradition To use this technique to prove a statement or theorem: oAssume that the theorem is false oFrom this assumption, show how it implies that some known (i.e. axiomatic) property is false oSince this would lead to a contradiction, the original assumption must be erroneous, so the theorem is true

Proof by contradiction example Theorem: There are an infinite number of primes Proof: o Suppose the theorem is false. Then there are a finite number of primes o Therefore, you can list them. Let the primes be P1, P2, ... , Pkbe the finite list of primes, from smallest to largest. (i.e. Pkis the largest prime) o Consider N = P1P2P3...Pk+ 1 o Clearly, N is larger than Pk(which is the largest prime), so N must not be prime o However, none of the primes in the list divides N exactly, because the remainder is always 1 o This contradicts the known property that every number is either prime or a product of primes o Therefore the assumption (finite primes) is false, implying the theorem is true

Proof by counterexample This is the easiest way to prove a given assertion to be false. oFor a statement to be true, it must be true in all cases oProvide one counterexample. This will show that in at least one case, the assertion does not hold (therefore, it's false)

Proof by counter example For the Fibonnaci series defined earlier, is the following true of false: ?? ?2 o?2= 2 22, ?3= 3 32,?4= 5 42 o?5= 8 52,?6= 13 62,?7= 21 72 o?8= 34 82,?9= 55 92,?10= 89 102 o?11= 144 > 121 = 112 counterexample o?? ?2 is false!