(a) Use mathematical induction to prove that log2 n ≤ n for all integers n ≥ 1. |

Use the result in part (a) to show that
3n + log2 n is Θ(n). |

## Expert Answer

By Induction;

**1) First of all we have prove it true for n=1**

log 1 = 0 < =1

**2)** Now let us assume that this inequality is true for n=k

Hence , log k <= k

**3)** Now we have to prove this inequality true for n=k+1

log (k+1) < = k+1

log (k+1) – log 2 <= k

log [(k+1) /2] < = k

(k+1) /2 <= k for all k > 0

log [(k+1) /2] <= log (k) =>

log k < k, log [(k+1) /2] < k

**b)** As we have proved that log n<=n

3n+logn <= 3n + n

hence

3n + log2 n = Θ(n).