A sharp Stirling's approximation form states that n ! &#x223C;<!-- ∼ -->

Hailie Blevins

Hailie Blevins

Answered question

2022-06-07

A sharp Stirling's approximation form states that
n ! ( n e ) n 2 π n .
Use that form to show that:
( 2 m m ) = Θ ( 2 2 m m ) .

Answer & Explanation

Braylon Perez

Braylon Perez

Beginner2022-06-08Added 34 answers

Using Stirling’s approximation, we have
( 2 n n ) = ( 2 n ) ! n ! 2 2 π ( 2 n ) ( 2 n / e ) 2 n ( 2 π n ( n / e ) n ) 2 = 2 π n 2 2 n ( n / e ) 2 n 2 π n ( n / e ) 2 n = 2 2 n π n ; it only remains to show that this approximation is good enough to justify the claim that ( 2 n n ) is Θ ( 2 2 n π n ) For this you have to understand that f ( n ) g ( n ) means that lim n f ( n ) g ( n ) = 1. Thus, we’re given not just that n! is approximately 2 π n ( n e ) n , but that
lim n n ! 2 π n ( n e ) n = 1 .
Thus,
( 2 n ) ! n ! 2 2 π ( 2 n ) ( 2 n / e ) 2 n ( 2 π n ( n / e ) n ) 2 = ( 2 n ) ! 2 π ( 2 n ) ( 2 n / e ) 2 n ( 2 π n ( n / e ) n ) 2 n ! 2 1 2 = 1
as n , i.e.,
( 2 n n ) 2 2 n π n .
You shouldn’t have much trouble showing that if f ( n ) g ( n ), then f ( n ) is Θ ( g ( n ) ) , which gives you your result; just use the definitions of limit and Θ.
Averi Mitchell

Averi Mitchell

Beginner2022-06-09Added 8 answers

( 2 m m ) = ( 2 m ) ! ( m ! ) 2 ( 2 m e ) 2 m 4 π m ( ( m e ) m 2 π m ) 2
Since
0.5 2 2 m m 2 2 m π m 2 2 2 m π m

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?