MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'd like to know the asymptotic behaviour as $N\to\infty$ of the following sum

$$ Z_N(x) := 2^{-N/2} \sum_{k=0}^{N/2} \frac{N!}{k! (N-2k)!} (N-1)^{-k} (\sqrt{2} x)^{N-2k} $$

in order to compute $p(x):=\lim_{N\to\infty} \frac{log(Z_N(x))}{N}$ with $x\geq0$ (I already know this limit exists) .

I found the lower bound $p(x)\geq\log(x)$, that by graphical simulations seems to be very good when $x$ is big enough.

Can you help me to compute $p(x)$?

share|cite|improve this question
Since $\lim_{N\to\infty}\frac{\log N}{N}=0$, you need just the largest term in the sum, which you can easily determine by comparing each term to the next. After that, Stirling finishes the story in no time. Voting to close as "too localized". – fedja Jun 2 '12 at 17:44
I really can't see why should I need only the largest term in the sum: could you give more details? – user22980 Jun 2 '12 at 18:03
up vote 6 down vote accepted

Let $T_N(x)$ denote the largest term of the sum. Note that $$\frac{\log T_N(x)}{N}\leq \frac{\log (Z_N(x))}{N}\leq \frac{\log ((N/2)T_N(x))}{N}=\frac{\log T_N(x)}{N}+\frac{\log(N/2)}{N}$$ and that the limits of both sides are identical, so by Squeeze theorem $p(x)=\lim\limits_{N\to\infty} \frac{\log(T_N(x))}{N}$. To find the largest term, we4 want to minimize the expression $k!(N-2k)!(N-1)^k(\sqrt{2}x)^{2k-N}$. Note that $$\frac{(k+1)!(N-2k-2)!(N-1)^{k+1}(\sqrt{2}x)^{2k+2-N}}{k!(N-2k)!(N-1)^k(\sqrt{2}x)^{2k-N}}=\frac{2x^2(k+1)(N-1)}{(N-2k-1)(N-2k)}$$ and so we continue to make the denominator smaller by increasing $k$ so long as $2x^2(k+1)(N-1)<(N-2k-1)(N-2k)$. Solving for $k$ (and making approximations valid for large $N$) gives $$\begin{align}k &< \frac{N x^2+2N-x^2-1-\sqrt{N^2x^4+4N^2x^2-2Nx^4+2Nx^2+x^4-6x^2+1}}{4}\\\\ &< \frac{N x^2+ 2N-\sqrt{x^4+4x^2}N}{4}=\frac{2+x^2-\sqrt{x^4+4x^2}}{4}N\\\\ \end{align}$$ and so for large $N$ the largest term will be $k=f(x)N$, with $f(x)=\frac{2+x^2-\sqrt{x^4+4x^2}}{4}$. Note that we can assume equality (rather than accuracy to the nearest integer) without hurting our calculations since the limit exists and for any $\epsilon$ we have arbitrarily large $N$ such that this is within $\epsilon$ of an integer. Thus $$T_N(x) = 2^{-N/2}\frac{N!}{(f(x)N)!((1-2f(x))N!)}(N-1)^{-f(x)N}(\sqrt{2}x)^{(1-2f(x))N}$$ and so taking logarithms and applying Stirling's approximation ($\log(y!)\approx y\log(y)-y$) we get $$\begin{align}\log(T_N(x)) &= -\frac{N}{2}\log(2)+\log(N!)-\log((f(x)N)!)-\log((1-2f(x))N!)\\\\ & \;\;\;\;-f(x)N\log(N-1)+(1-2f(x))N\log(\sqrt{2}x)\\\\ &\approx -\frac{N}{2}\log(2)+N\log(N)-N-f(x)N\log(f(x)N)+f(x)N\\\\ & \;\;\;\;-(1-2f(x))N\log((1-2f(x))N)+(1-2f(x))N-f(x)N\log(N-1)\\\\ & \;\;\;\;+(1-2f(x))N\log(\sqrt{2}x)\\\\ \end{align}$$ and so (note we make the approximation $\log(N-1)\approx \log(N)$) $$\begin{align} \frac{\log(T_N(x))}{N}&\approx -\frac{\log(2)}{2}-f(x)+\log(N)-f(x)\log(f(x)N) \\\\ & \;\;\;\;-(1-2f(x))\log((1-2f(x))N)-f(x)\log(N-1)\\\\ & \;\;\;\;+(1-2f(x))\log(\sqrt{2}x)\\\\ &\approx -\frac{\log(2)}{2}-f(x)+\log(N)-f(x)\log(f(x))-f(x)\log(N) \\\\ & \;\;\;\;-(1-2f(x))\log(1-2f(x))-(1-2f(x))\log(N)-f(x)\log(N-1)\\\\ & \;\;\;\;+(1-2f(x))\log(\sqrt{2}x)\\\\ &\approx -\frac{\log(2)}{2}-f(x)-f(x)\log(f(x))-(1-2f(x))\log(1-2f(x))\\\\ & \;\;\;\;+(1-2f(x))\log(\sqrt{2}x)\\\\ \end{align}$$ thus $$\begin{align} p(x) &= \lim\limits_{N\to\infty} \frac{\log(T_N(x))}{N}\\\\ &\approx -\frac{\log(2)}{2}-f(x)(1+\log(f(x)))+(1-2f(x))(\log(\sqrt{2}x)-\log(1-2f(x)))\\\\ \end{align}$$ which should be quite close to the actual value due to the accuracy of Stirling's for large values.

share|cite|improve this answer
Thanks a lot! The idea seems to work, I made a plot and your result is quite different from the real limit: I shall check the computations.. I'll let you know – user22980 Jun 2 '12 at 20:51
It is very possible I made a computational error (or in the case of solving for the optimal $k$, a Mathematica error) in the lengthy string of computations. I hope it doesn't sink things! – Alex Becker Jun 2 '12 at 20:53
It should actually be $f(x)=\frac{2+x^2-\sqrt{x^4+4x^2}}4$ (the factor $2x^2$ went to the wrong side). Other than that, it's correct. – fedja Jun 2 '12 at 23:33
@fedja I'm not seeing the error. Since $$\frac{(\sqrt{2}x)^{2k-2-N}}{(\sqrt{2}x)^{2k-N}}=\frac{1}{2x^2}$$ isn't the $2x^2$ on the correct side? – Alex Becker Jun 2 '12 at 23:53
And where exactly did the power $2k-2-N$ in the numerator come from? I thought we were comparing $k$ to $k+1$, not to $k-1$... – fedja Jun 3 '12 at 2:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.