Question

Please note n's are superscripted.

(a) Use mathematical induction to prove that 2ⁿ⁺¹ + 3ⁿ⁺¹ ≤ 2 · 4ⁿ for all integers n ≥ 3.

(b) Let f(n) = 2ⁿ⁺¹ + 3ⁿ⁺¹ and g(n) = 4ⁿ. Using the inequality from part (a) prove that f(n) = O(g(n)). You need to give a rigorous proof derived directly from the definition of O-notation, without using any theorems from class. (First, give a complete statement of the definition. Next, show how f(n) = O(g(n)) follows from this definition.)

Answer 1

a)For n=3:

n=3:

The inequality is true for n=3.

For n=k>3

Let this be equation (1).

For n=k+1

Hence from above equation and equation 1 it is true that the inequality holds true for all k>=3.

b)f(n)=2n+1+3n+1 and g(n)=4n

For and any c greater than 1.