USA: +1 (725) 712-1730 
Sign in
| (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).
