1. F(0) = 0; F(1) = 1; F(2) = 1; F(3) = 2; F(4) = 3; F(5) = 5; F(n) = F(n-1)+F(n-2). F(-1) = 1. F(-2) = -1. f(n) = f(n-1) + f(n-2) x^2 = x + 1 x^2 -x -1 = 0. Phi "The Golden Ratio" is defined being (1+sqrt(5))/2. Phihat is defined as being (1-sqrt(5))/2. 1 0 -1 0 1 0 -1 0 1 0 -1 0 f(x) = cos (x pi/2) f(0) = 1 f(1) = 0 f(x) = -f(x-2) x^2 = -1 x = i, -i Ci^x + D(-i)^x (1+sqrt(5))^2 FOIL (a+b)^2 = a^2 + 2ab + b^2 1 + 2sqrt(5) + 5 = 6 + 2sqrt(5) (1+sqrt(5))/2 <== Take the reciprocal of this My favorite mistake sqrt(2)/2 = sqrt(). 2 / (1+sqrt(5)) = 2(1-sqrt(5)) / (1+sqrt(5)) (1-sqrt(5)) (a+b)(a-b) = a^2 - b^2 2(1-sqrt(5))/(1-5) = 2(1-sqrt(5))/(-4) = -(1-sqrt(5))/2 = -PhiHat Phi = 1.618 PhiHat = -0.618 Prove that: n^k = o (c^n) for k>=0 and for c>1. lim{n->inf} (n^k / c^n) = 0 By induction: Base case: k = 0 lim{n->inf} (n^0 / c^n) = lim{n->inf} (1 / c^n) 1/inf = 0. Induction, assume it works for all values < k. Prove it works for k. lim{n->inf} (n^k / c^n) = inf/inf, indeterminate case. 5/0 is very different from 0/0. What 0/0 means x 0 = 0, what might x be? 5/0 means x 0 = 5, what could x be? k*n^(k-1) / ln(c) * c^n = (k/ln c) n^(k-1) / c^n. ==> (k/ln c)*0 = 0 Tangential comment: log mean log_10 ln = log_e lg = log_2. lg n = THETA (ln n) ln^k (n) = o (n^c), c > 0. Show it's true for k=0. (BASE CASE) ln^0(n) = 1. lim[n->inf] 1/ n^c ==> 0 Assume it's true for integers < k. Prove it's true for k. lim[n->inf] ln^k(n) / n^c ==> inf/inf, indeterminate case (ln n)^k k(ln n)^(k-1) 1/n = k/n ln^(k-1)(n). c n^(c-1) = cn^c / n k/n ln^(k-1)(n) / cn^c / n = k ln^(k-1)(n) / cn^c = (k/c) ln^(k-1)(n) / n^c ==> (k/c) 0 ==> 0. Now to do that homework problem on Fibonaccis. The easiest way is with TWO base cases. Show that it works for F(0), and for F(1), and then do the induction case. You need to remember that F(n) = F(n-1)+F(n-2) and you will probably have to apply the inductive assumption twice. Prove by induction that in any collection of cows, all cows are the same color. Base case: one cow in the collection. Of course it is the same color as itself. Inductive case: Assume it's true for collections of less than k cows. Prove it's true for k cows. Remove one cow from the collection. This collection of k-1 cows are all the same color, by assumption. Put that cow back and remove a different cow. THOSE k-1 cows are all the same color by assumption. So, all k cows must be the same color as each other. tricolor: red/green<==>bicolor monochrome<==>unicolor blind<==>no color Binary Search: Search (A,x): (A is sorted) if A is empty, NOT FOUND Choose middle element of A. If that element is equal to x, FOUND if x < that element Search (first half of A, x) else Search (Second half of A, x) What is the runtime of this? THETA (lg n). BUT you don't have to say "log base 2" because all logs are THETA of each other anyway. But how do you know this: The size of the array is n. The next level of recursion the size of the array is n/2. The next level has size n/4, and so forth, and so on, until you get to the array having size 1. n/ 2^k = 1 ==> 2^k = n ==> k = lg n. Notice that I'm doing a constant amount of work at each level, and there are lg n levels, so I conclude that the total amount of work is THETA (lg n).