Please answer the 4th question.

I. (2 points) Let F, be the Fibonacci numbers, where Fo= l, F,-I, F2-2, F,-3, F. = 5 . Prove -2 F1 = FN-2, where N> 2 using induction. (Lipschutz, HW 3) 2 C2 points) Use induction to prove that fr all natural numbersas divisible by x-1. Heileman, p.415) 3. (2 points) Prove by induction that l 2 + 22 + 32 + + n2 4. (2 points) Prove by induction that the sum of the first n odd positive integers is n, i.e., 1 +3+5 (2n)-r 5, (2 points) Prove that -ok2k-(n-1)2n+1 + 2. (Heileman, p. 415) 6. (2 points) Assuming a and b are arbitrary constants, and 0 no. (Goodrich, p.185) 8. (4 points) Prove that x2 + 3x-10 is (N) This actually involves two proofs (Lipshutz HW 3) 9. (4 points, 2 points each) Assuming that fi(n) is Og(n)) and fa(n) is O(g2(n)): (Drozdek, p.71) a. Find a counterexample to refute that fin-fi(n) is O(gfn_gz(n)) by supply ingfi./. g, and g2. b. Find a counterexample to refute that/,(n) (n) is O(g,(n) /82(n)) by supplyingfi./, g, and g2. 10. (2 points) Show that log(n + 1) = 0(log n). (Heileman p.28)