n → ∞ lim n 2 ( ( 1 + n + 1 1 ) n + 1 − ( 1 + n 1 ) n ) = ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Clever use of taylor series
its all about approximations and understanding the growth of functions. this is very useful in complexity theory. they study the time taken by the algorithm. they express this growth using the o notation. polynomial time algorithms means time taken is o(n^k), where k is a natural number.
We apply the mean value theorem to f ( x ) = ( 1 + x 1 ) x on [ n , n + 1 ] to give a function ε : ( 0 , ∞ ) → ( 0 , 1 ) such that f ( n + 1 ) − f ( n ) = f ′ ( n + ε ( n ) ) ( ( n + 1 ) − n ) = ( 1 + n + ε ( n ) 1 ) n + ε ( n ) ( ln ( 1 + n + ε ( n ) 1 ) − n + ε ( n ) + 1 1 )
Now, since 0 < ε ( n ) < 1 implies lim n → ∞ ( n + ε ( n ) ) 2 n 2 = 1 , it follows that n → ∞ lim n 2 ( ( 1 + n + 1 1 ) n + 1 − ( 1 + n 1 ) n ) = n → ∞ lim ( n + ε ( n ) ) 2 ( 1 + n + ε ( n ) 1 ) n + ε ( n ) ( ln ( 1 + n + ε ( n ) 1 ) − n + ε ( n ) + 1 1 ) = x → ∞ lim x 2 ( 1 + x 1 ) x ( ln ( 1 + x 1 ) − x + 1 1 ) where this last equality is true as long as the last limit exists. To evaluate it, we can use the fact ( 1 + x 1 ) x → e along with one application of L'Hopital's rule: x → ∞ lim x 2 ( 1 + x 1 ) x ( ln ( 1 + x 1 ) − x + 1 1 ) = e ⋅ x → ∞ lim x 2 1 ln ( 1 + x 1 ) − x + 1 1 = e ⋅ x → ∞ lim − x 3 2 x + 1 1 − x 1 + ( x + 1 ) 2 1 = e ⋅ x → ∞ lim 2 ( x + 1 ) 2 x 2 = e ⋅ 2 1 = 2 e ≈ 1 . 3 5 9 1 4 0 9 1
Note: In this case, f ′ ′ ( x ) < 0 for all x > 0 , so ε is uniquely defined. Even for general functions f satisfying the assumptions of the mean value theorem, we can always choose such a function ε by the axiom of choice.
Problem Loading...
Note Loading...
Set Loading...
Note that n 2 [ ( 1 + n + 1 1 ) n + 1 − ( 1 + n 1 ) n ] = n 2 ( 1 + n 1 ) n [ ( n + 1 ) 2 n + 1 ( n + 2 ) n + 1 n n − 1 ] = n 2 ( 1 + n 1 ) n [ n n + 1 ( 1 − ( n + 1 ) 2 1 ) n + 1 − 1 ] Now ln ( 1 − ( n + 1 ) 2 1 ) ( n + 1 ) ln ( 1 − ( n + 1 ) 2 1 ) ( 1 − ( n + 1 ) 2 1 ) n + 1 n n + 1 ( 1 − ( n + 1 ) 2 1 ) n + 1 n 2 [ n n + 1 ( 1 − ( n + 1 ) 2 1 ) n + 1 − 1 ] = − ( n + 1 ) 2 1 + o ( n − 3 ) = − n + 1 1 + o ( n − 2 ) = e − n + 1 1 + o ( n − 2 ) = 1 − n + 1 1 + 2 ( n + 1 ) 2 1 + o ( n − 2 ) = 1 + 2 n ( n + 1 ) 1 + o ( n − 2 ) = 2 ( n + 1 ) n + o ( 1 ) as n → ∞ . Thus we deduce that n → ∞ lim n 2 [ ( 1 + n + 1 1 ) n + 1 − ( 1 + n 1 ) n ] = 2 1 e