Proof of Inductive Hypothesis lg(n) = O(n)

[Noor01]

Hello,

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ⁿ , 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ⁿ⁺¹= 2 · 2ⁿ> 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 finished.
So we take c = 1 and n0 = 1
_______________________________________

I don't know how we got this answer in these two lines:
1)2ⁿ⁺¹= 2 · 2ⁿ> 2n
2)2n ≥ n + 1 ⇐⇒ n ≥ 1,

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

thxx

 

[mmwave]

Thank you for your question about the inductive hypothesis with asymptotic notation. I am happy to help clarify this example for you.

Firstly, let's define the inductive hypothesis in this context. The inductive hypothesis is a method of mathematical proof that uses the concept of induction to show that a statement holds for all values of a certain variable. In this case, the variable is n, and we want to prove that the statement lg(n) < n holds for all n ≥ 1.

Now, let's break down the two lines that you have questions about:

1) 2n+1 = 2 · 2n > 2n
This line is simply using the fact that 2n+1 is equal to 2 multiplied by 2n, and since 2 is greater than 1, we can conclude that 2n+1 is greater than 2n. This is important because it helps us show that the statement holds for n+1 when we are using induction.

2) 2n ≥ n + 1 ⇐⇒ n ≥ 1
This line is showing the reverse implication of the statement. If we assume that the statement is true for n, then we can show that it is also true for n+1. This is important for the induction step in the proof.

I hope this helps clarify the example for you. Please let me know if you have any further questions or if you need more explanation. Happy to help!