Asymptotics of a hypergeometric series/Taylor series coefficient.

Question

I was planning on figuring this problem out for myself, but I also wanted to try out mathoverflow. Here goes:

I wanted to know the asymptotics of the sum of the absolute values of the Fourier-Walsh coefficients of the "Majority" function on 2n+1 binary inputs. Long story short, that boiled down to finding the asymptotics of the following quantity:

L[n] := sum{k=0..n} F[n,k],

where

F[n,k] := (2n+1)!! / [(2k+1) k! (n-k)!].

Here is the set of steps that a naive person such as me always follows in such a scenario:

Step 1. Type it into Maple. In this case, Maple reports back

L[n] = ( (2n+1) (2n choose n) / 2^n ) hypergeom([1/2, -n], [3/2], -1).

I don't know exactly what this hypergeom is, nor how to evaluate its asymptotics. I can't seem to get Maple to tell me (with asympt()) either.

Step 2. Evaluate the first few terms (1, 4, 14, 48, 166, 584, 2092, etc.) and type it into OEIS. It's clearly sequence A082590. There are many definitions given for this sequence; One definition is (basically) the above hypergeometric formula. Another is that it is

2^n sum{k=0..n} 2^(-k) (2k choose k).

Given this, it's pretty easy to deduce from Stirling that the rough asymptotics is Theta(2^(2n) / sqrt(n)). Actually, I originally didn't notice this simple definition on the OEIS page. Instead, the simplest thing I noticed was the title definition,

the [x^n] coefficient of 1/((1-2x) sqrt(1-4x)).

Since that was the simplest thing I initially noticed, I wondered how to find the asymptotics of that. I was sure many people would know that, but mathoverflow didn't exist at the time. So...

Step 3. Email Doron Zeilberger out of the blue, asking for help. He very kindly responded: "You could use the contour integral... or my favorite way would be to use my Maple packages:

read AsyRec: read EKHAD: Asy(AZd( 1/(1-2*x)/(1-4*x)^(1/2)/(x^(n+1)),x,n,N)[1],n,N,2);

which produces

2^(2*n)(1/n)^(1/2)(1+3/8/n+121/128/n^2)."

Great! There's the precise answer! But I don't know much about how Zeilberger's packages work, don't know what the contour integral is, and anyway, it's all roundabout story.

If you were writing this in a paper, what would be the shortest way to go from the definition of L_n to the fact

L[n] = (2^(2n) / sqrt(n)) (1+o(1))?

Answer 1

Okay, you want the asymptotics of

[z^n] 1/((1-2z) sqrt(1-4z)).

In a neighborhood of z = 1/4, you have

1/((1-2z) sqrt(1-4z)) = 2/sqrt(1-4z) * (1+o(1))

Then a theorem of Flajolet and Odlyzko (see Flajolet and Sedgewick, Analytic Combinatorics, Cor. VI.1; the book is available for free download from Flajolet's web site tells you that

[z^n] 1/((1-2z) sqrt(1-4z)) = (1+o(1)) * 2 [z^n] (1-4z)^{-1/2}.

This is the well-known generating function for the sequence of central binomial coefficients C(2n, n). So [z^n] (1-4z)^{-1/2} = 4^n / sqrt(Pi*n) * (1+o(1)). Therefore

[z^n] 1/((1-2z) sqrt(1-4z)) = 4^n/sqrt(n) * 2/sqrt(Pi) * (1+o(1)).

For further development of the asymptotic series, read Chapter 6 of Flajolet and Sedgewick.

Answer 2

(A sketch of) an alternative way to get the asymptotics directly from the definition of L[n]:

After some manipulations, we can write F(n, k)=[(2n+1)!/(n!^2 2^n)] [(n choose k)/(2k+1) )].

The next task is to estimate the sum of the second bracketed term. Since all but an exponentially small fraction of the mass of (n choose k) is contained at k=n/2+o(n), we can write

sum_k [(n choose k)/(2k+1) )] = (1+o(1))[2^n / n].

Plugging this in to the formula for F(n,k), we have

L(n)= (1+o(1)) (2n+1)!/(n!^2 * n)=(1+o(1)) [(n+1)/n] (2n+1 choose n), and Michael's estimate now follows from the standard asymptotics for the central binomial coefficient.

Answer 3

It may be worth pointing out that when you can't find an easy way to transform the desired asymptotic into one you already know how to compute, it may be worth considering using Hayman's method (which has a tendancy to give you asymptotic formulae with a sqrt(pi) in them). Hayman's method tends to work when you want an asymptotic for the coefficients of a generating function which is largest on the positive real axis. To learn the method, Hayman's original article "A generalisation of Stirling's formula" is very readable.