# maybe this sum have approximation $\sum_{k=0}^{n}\binom{n}{k}^3\approx\frac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty$

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

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.

• Nice job! (+1). – Ron Gordon Feb 2 '14 at 22:52

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.

• +1 This is also the hand waving way I have to get this result. – achille hui Feb 2 '14 at 19:02
• @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. – Felix Marin Aug 12 '14 at 20:00
• @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. – achille hui Aug 12 '14 at 20:12
• @achillehui I'll recheck that to add some 'hand savings' arguments. Thanks. – Felix Marin Aug 12 '14 at 20:13