All the three questions please 39,41,45

45. Prove that the set of all prime numbers is infinite. 41. Show that 2 V2 is irrational. 39. The Fibonacci sequence is defined recursively by f(n + 2) = f(n + 1) + f(n), n = 1, 2, ..., with f(1) = 1, F(2) = 1. Show that (a) f(n) = O(2"), (b) f(n) = 12(1.5")