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**

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?

Draft saved
Draft deleted

Loading...

Similar Threads for Inductive hypothesis |
---|

I Hilbert's omega rule, induction, omega-consistency |

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