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))?
Best Answer
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.