4. [10 points] The Fibonacci sequence is defined by fo = 0, f1 = 1, f2 = 1, fn = fn-1 + fn-2 (n>3). Its first few terms are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Prove that for all n > 1: n [fi = fn+2 - 1. i=1 5. [10 points] Let A1, A2, ..., An be sets. Prove that for every integer n 2 1, we have: (Al UA2 U . . . UAn) = AfnAn . . . nA. 6. [10 points] Let an be the sequence defined by a1 = 1, a2 = 8, an = an-1 + 2an-2 for n 2 3. Prove that an = 3 . 27-1 + 2(-1)" Vn >1