1. Evaluate the following sums: (2 points) 00 1 00 i 2. Use proof by induction in class: (2 points) Prove the following formulas 3. Give a big-0 estimate that is simple and effective for each of the functions: (2 points) (a) n2logn 3n2 +5 m+Tn 4. Given functions A and B, fill in the table with "true" or "false" in each table cell. Assume that k>-1, and c>1 are constants. (3 points) A- A (B) 1l 72 Vnnn) lg(c) g(n) lg(n!)lg(n") 5. Which of the following is false? (1 point) (a) If Tm)-O then T(n) is no greater than that of g(n) (b) If T(n)-lg),then T(n) is no smaller than that of g(n) (c) log10(n) -0(n2)