4
$\begingroup$

prove or disprove this $$\sum_{k=0}^{n}\binom{n}{k}^3\approx\dfrac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty?$$

this problem is from when Find this limit $$\lim_{n\to\infty}\dfrac{\displaystyle\sum_{k=0}^{n}\binom{n}{k}^3}{\displaystyle\sum_{k=0}^{n+1}\binom{n+1}{k}^3}=\dfrac{1}{8}?$$

first,follow I can't $$\sum_{k=0}^{n}\binom{n}{k}^3\approx\dfrac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty?$$ .Thank you for you help

$\endgroup$
7
$\begingroup$

Let $\;\displaystyle\text{Fr}_n = \sum\limits_{k=0}^n \binom{n}{k}^3\;$ be the $n^{th}$ Franel number (OEIS A000172 ).

Combinatorially, it is the sum of those coefficients in following polynomial expansion where the power of $x, y, z$ are all the same.

$$(1+x)^n (1+y)^n (1+z)^n = \sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^n \binom{n}{i}\binom{n}{j}\binom{n}{k} x^i y^j z^k $$

More precisely, $$\text{Fr}_n = \sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^n \binom{n}{i}\binom{n}{j}\binom{n}{k} \delta_{ij}\delta_{jk}$$ where $\delta_{ij}$ is the Kronecker delta. Using following integral representation of Kronecker delta,

$$\delta_{pq} = \int_{-\pi}^{\pi} e^{i(p-q)\theta} \frac{d\theta}{2\pi}$$ We can derive an integral representation of $\text{Fr}_n$:

$$ \text{Fr}_n = 8^n \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} f(\theta,\phi)^n \frac{d\theta d\phi}{4\pi^2} \quad\text{ where }\quad f(\theta,\phi) = \left(\frac{\cos\theta+\cos\phi}{2}\right)\cos\theta $$ Over its domain $[-\pi,\pi]^2$, $f(\theta,\phi)$ varies between $-\frac18$ and $1$. If we let $\rho(t)$ be the "density" where $f(\theta,\phi)$ taking the value $t$. We can simplify above expression as

$$\text{Fr}_n = 8^n \int_{-\frac18}^1 t^n \rho(t) dt$$

For large $n$, the weight of the $t^n$ factor in above integral will be concentrated at $t \sim 1$. We just need to figure out the behavior of $\rho(t)$ there. The contribution from other parts of the interval will be exponentially suppressed.

Introduce variables $x = \cos\theta$ and $y = \cos\phi$. For $t \sim 1$, we have

$$\begin{align}\rho(t) = &\frac{1}{4\pi^2}\int_{-\pi}^{\pi}\int_{-\pi}^{\pi} \delta(f(\theta,\phi)-t) d\theta d\phi\\ = & \frac{1}{\pi^2}\int_{-1}^1\int_{-1}^1 \frac{\delta\left(\left(\frac{x+y}{2}\right)x-t\right) dx dy}{\sqrt{(1-x^2)(1-y^2)}}\\ = & \frac{2}{\pi^2}\int_{\frac{\sqrt{1+8t}-1}{2}}^1 \frac{\frac{2}{x} dx}{\sqrt{(1-x^2)\left(1-\left(\frac{2t}{x}-x\right)^2\right)}} \end{align}$$ Let $u = \frac{\sqrt{1+8t}-1}{2}$. Introduce variable $z, w$ such that $z = x^2 = u^2 + (1-u^2)w$, we can simplify above as

$$\begin{align} \rho(t) = &\frac{4}{\pi^2}\int_{u}^1 \frac{dx}{\sqrt{(1-x^2)(x^2-u^2)((1+u)^2-x^2)}}\\ = &\frac{2}{\pi^2}\int_{u^2}^1 \frac{dz}{\sqrt{z(1-z)(z-u^2)((1+u)^2 - z)}}\\ = &\frac{2}{\pi^2}\int_{0}^{1} \frac{dw}{\sqrt{w(1-w)(u^2+(1-u^2)w)(1+2u-(1-u^2)w)}} \end{align}$$ Let $t = 1-\epsilon$ and Taylor expand the integrand in terms of $\epsilon$. We get

$$\begin{align} \rho(1-\epsilon) \approx & \frac{2}{\pi^2\sqrt{3}}\int_{0}^{1}\frac{dw}{\sqrt{w(1-w)}} \left[ 1 - \frac{(4w-8) \epsilon}{9} + \frac{(48w^2-92w+70) \epsilon^{2}}{81} + \ldots \right]\\ = & \frac{2}{\pi\sqrt{3}}\left[ 1 + \frac23 \epsilon + \frac{14}{27}\epsilon^2 + \frac{104}{243}\epsilon^3 + \frac{266}{729}\epsilon^4 + \ldots \right] \end{align}$$ Introduce yet another variable $\lambda$ such that $t = e^{-\lambda}$, above expansion implies near $\lambda \sim 0$.

$$\rho(e^{-\lambda})e^{-\lambda} \sim \frac{2}{\pi\sqrt{3}}\left[ 1 - \frac{\lambda}{3} + \frac{\lambda^2}{54} + \frac{\lambda^3}{486} + \frac{\lambda^4}{5832} + \ldots \right]$$

In terms of $\lambda$, the integral representation of $\text{Fr}_{n}$ is now in a form which we can apply Watson's Lemma. As a result, we obtain following asymptotic expansion of $\text{Fr}_n$:

$$\begin{align} \text{Fr}_n = & 8^n \left\{ \int_0^\Lambda e^{-n\lambda} \rho(e^{-\lambda})e^{-\lambda} d\lambda + O\left(\max\left( e^{-\Lambda}, \frac18 \right)^n\right) \right\} \\ \stackrel{asy}{\sim} & 8^n \frac{2}{\pi\sqrt{3}n}\left[ 1 - \frac{1}{3n} + \frac{1}{27n^2} + \frac{1}{81n^3} + \frac{1}{243n^4} + \ldots \right]\tag{*1} \end{align}$$

where $\Lambda$ is some cutoff for $\lambda$ where the Taylor expansion of $\rho(e^{-\lambda})e^{-\lambda}$ is valid.

Actually, once we figure out the leading behavior of $\text{Fr}_n$, there is a simpler way to derive above expansion. Franel has shown $\text{Fr}_{n}$ satisfy following recurrence relation:

$$n^2 \text{Fr}_n = (7n^2-7n+2) \text{Fr}_{n-1} + 8(n-1)^2 \text{Fr}_{n-2}\tag{*2}$$

If one write down a formal expansion of $\text{Fr}_n$ of the form

$$\text{Fr}_n = 8^n \frac{2}{\pi\sqrt{3}n}\left[ 1 + \frac{\beta_1}{n} + \frac{\beta_2}{n^2} + \ldots\right]$$

Plug this in $(*2)$ and match the coefficients, one will obtain:

$$\text{Fr}_n = 8^n \frac{2}{\pi\sqrt{3}n}\left[ 1 -\frac{1}{3n} +\frac{1}{3^3n^2} +\frac{1}{3^4n^3} +\frac{1}{3^5n^4} +\frac{11}{3^7n^5} +\frac{49}{3^9n^6} -\frac{317}{3^9n^7}\\ -\frac{2797}{3^{10}n^8} -\frac{61741}{3^{13}n^9} +\frac{734467}{3^{14}n^{10}} + \ldots \right]$$

An expansion consistent what we have got by other means and appeared in answers in a nearly the same question.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice job! (+1). $\endgroup$ – Ron Gordon Feb 2 '14 at 22:52
8
$\begingroup$

I would begin by noting that one may approximate a binomial distribution for large $n$ by a normal distribution as follows:

$$\binom{n}{k} p^k (1-p)^{n-k} \sim \frac1{\sqrt{2 \pi n p (1-p)}} e^{-(k-n p)^2/(2 n p (1-p))}$$

For $p=1/2$ this simplifies to

$$\frac1{2^n} \binom{n}{k} \sim \sqrt{\frac{2}{\pi n}} e^{-2 (k-n/2)^2/n}$$

Note that a sum over $k$ on the left and an integral over $k$ on the right both equal $1$.

Now cube the above equation, and integrate the right-hand side over $k$:

$$\begin{align}\frac1{8^n} \sum_{k=0}^n \binom{n}{k}^3 &\sim \left ( \frac{2}{\pi n} \right )^{3/2} \int_{-\infty}^{\infty} dk \, e^{-6 (k-n/2)^2/n}\\ &= \left ( \frac{2}{\pi n} \right )^{3/2} \sqrt{\frac{n \pi}{6}}\\ &= \frac{2}{\sqrt{3} \pi n}\end{align}$$

The stated result follows.

I will state that this is hardly a rigorous way of proving the result, but simply follows from a consequence of the central limit theorem.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 This is also the hand waving way I have to get this result. $\endgroup$ – achille hui Feb 2 '14 at 19:02
  • $\begingroup$ @achillehui I did something like that and some people has been pushing to delete that answer. Indeed, this answer ( ${\tt\mbox{@Ron Gordon}}$ one ) is quite fine. $\endgroup$ – Felix Marin Aug 12 '14 at 20:00
  • $\begingroup$ @FelixMarin Aside from you need to justify (or claim you are hand waving) at the second equality, everything is fine to me. I upvoted it to avoid it get deleted. $\endgroup$ – achille hui Aug 12 '14 at 20:12
  • $\begingroup$ @achillehui I'll recheck that to add some 'hand savings' arguments. Thanks. $\endgroup$ – Felix Marin Aug 12 '14 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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