a) Use basic algebra to show that k+1 2k for any k 1. (Easy)

b) Use Part a, along with the fact that log₂ is an increasing function to show that log₂ (k+1) log₂ (k) + 1 for k1. (Easy)

c) Prove by induction that log₂(n) n for all n 1. Use the result in Part b in your proof.

d) In fact, the inequality you proved in Part c, is true for all real numbers, not just integers, i.e. log₂(x) x for all x 1. Explain why the italicized statement establishes that log₂(x) is O(x), based on the definition of big O. (What are C and k?).

e) Show the same result as in Part d by taking a limit, including use of L'Hpital's rule. Make sure to take the limit correctly, for example, you may need the conversion formula log₂(x) = ln(x) / ln(2).