Hello,(adsbygoogle = window.adsbygoogle || []).push({});

I would like to ask a question that is related to the inductive hypothesis with Asymptotic notation.

__________________________________________

Example:

lg(n) = O(n)

Intuitively: lg(n) < n for all n ≥ 1.

Need a proof. Well

lg(n) < n ⇐⇒ n < 2^{n}, for all n > 0.

Use induction on n to prove rhs.

Base case n = 1 is clearly true.

For induction step assume claim holds for n. Then

2^{n+1}= 2 · 2^{n}> 2n, by induction hypothesis.

To complete the proof just need to show that 2n ≥ n + 1.

Now

2n ≥ n + 1 ⇐⇒ n ≥ 1,

and we have ﬁnished.

So we take c = 1 and n0 = 1

_______________________________________

I don't know how we got this answer in these two lines:

1)2^{n+1}= 2 · 2^{n}> 2n

2)2n ≥ n + 1 ⇐⇒ n ≥ 1,

If you can explain this example for me, I would really appreciate that.

thxx

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Inductive hypothesis

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**