Please Help!

1. Given following sequence 1 2 0 1 3 7 3 4 15 5 31 Tn 6 7 63127 8 255 Show the recurrence equation of this sequence Solve the recurrence by repeated substitution to show that In = 2" - 1. Must show at least 3 substitution steps!!! before deriving final answer. 2. Prove the following equation (don't use induction): log AB = Blog A. 3. Evaluate the following sums: 1. Li=0 2. 2+ 5 +8+ ... + (3N-1) 4. Write a recursive C++ function that returns the number of 1's in the binary representation of N. Use this fact: The number of 1's in N is equal to the number of 1's in N/2, except when N is odd where you need to add value 1. Include complete program including your test cases. Must test with multiple test cases!!! 5. Show that the insertion sort we discussed in class has worst case performance O(N2) 6. Prove the following equations using induction. 1. ^, xi = 2*+1 -1 2-1 2. :1 (2i 1) = N2 3. Prove using mathematical induction that for all n 2 1, 1+4+7+...+(3n - 2) = (n(3n - 1))/2 4. Prove using mathematical induction that for all n 2 1,12 + 22 + ... + n2 = ((n)(n+1)(2n+1))/6