3
$\begingroup$

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)$?

$\endgroup$
2
  • 1
    $\begingroup$ 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". $\endgroup$
    – fedja
    Jun 2, 2012 at 17:44
  • $\begingroup$ I really can't see why should I need only the largest term in the sum: could you give more details? $\endgroup$
    – user22980
    Jun 2, 2012 at 18:03

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$
    – user22980
    Jun 2, 2012 at 20:51
  • 1
    $\begingroup$ 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! $\endgroup$ Jun 2, 2012 at 20:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – fedja
    Jun 2, 2012 at 23:33
  • $\begingroup$ @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? $\endgroup$ Jun 2, 2012 at 23:53
  • $\begingroup$ 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$... $\endgroup$
    – fedja
    Jun 3, 2012 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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