Prove (log n)^2<=2^n by induction

zaviknuogg

zaviknuogg

Answered question

2022-09-24

Prove ( log n ) 2 2 n by induction
I've trying to solve this for quite a while now, but not being able to finish the proof.
Prove using induction that ( log n ) 2 2 n

Answer & Explanation

Lilliana Mason

Lilliana Mason

Beginner2022-09-25Added 11 answers

For n = 1 , 2 , 3 it's clearly true.
Assume that it holds for n = k: log k 2 n / 2
Then
log ( k + 1 ) = log k log ( k + 1 ) log k = log k ( 1 + log ( 1 + 1 k ) log k ) log k ( 1 + 1 k log k ) 2 n / 2 2 1 / 2 = 2 ( n + 1 ) / 2 ,
as
1 + 1 k log k 2 , for  n 3
videosfapaturqz

videosfapaturqz

Beginner2022-09-26Added 3 answers

Try this roadmap:
log n < n for all n
n 2 2 n for n 3
handle the case n = 3 separately.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?