N YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 2. (5+5 points) (a) Prove by mathematical induction that for all positive integers n Ck. 2k = (n -1). 2+1 + 2 (b) Prove by induction that 3" 6.YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 3 3. (5+5 points) (a) For the Fibonacci sequence defined recursively by fo = 0, f1 = 1, and fn+1 = fn + fn-1 for all n 2 1 prove by structural induction that fitf? + ... + fh = faint1 (b) Use Strong Induction to show that every positive integer n can be written as the sum of distinct powers of 2: 20 = 1, 21 = 2, 22 = 4, 23 = 8, etc. Hint: For the inductive step, separately consider the case where k + 1 is even, hence (k + 1)/2 is an integer, and where it is odd)