1.1 Prove the following formula by induction: sigma i=1 to N i^3 = (sigma i=1 to

Question

1.1 Prove the following formula by induction: sigma i=1 to N i^3 = (sigma i=1 to Ni)^2. You must show base case, inductive hypothesis and proof in your solution. 1.2 Write a recursive method that returns the number of 1?s in the binary representation of N. Use the fact that this is equal to the number of 1 ?s in the representation of N/2, plus 1, if N is odd. 1.3 Prove that sigma i=1 to N i x i! = (N + 1)! - 1 by induction. You must show base case, inductive hypothesis and proof in your solution. 1 .4 List the functions below from the lowest to the highest order. 1f any two or more are of the same order, indicate which. 1.5 For each of the following pairs of functions f(N) and g(N), determine whether f(N) =O(g(N)), g(N) = O(f(N)), or both. You must provide both answers and explanations for this question.

Explanation / Answer

Let n = 1. Then:

...and:

So (*) works for n = 1.

Assume, for n = k, that (*) holds; that is, that

     2 + 22 + 23 + 24 + ... + 2k = 2k+1

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.