Is there a closed form or approximation to $\sum_{i=0}^n\binom{\binom{n}{i}}{i}$

Solution 1:

Lets try to find the maximum of

$$f(i)=\binom {\binom ni}i$$

Consider $i\in \{n/4,3n/4\}$. In this range a good approximation (from the central limit theorem) is

$$\binom ni\simeq\frac{2^n}{\sqrt{\frac 12n\pi}}e^{-\frac{(i-n/2)^2}{n/2}}$$

This is far larger than $i$, so we have

$$f(i)=\binom {\binom ni}i\simeq\frac{\binom ni^i}{i!}\simeq\frac{2^{ni}}{i!(\frac 12n\pi)^{i/2}}e^{-\frac{i(i-n/2)^2}{n/2}}$$

Taking logarithms and using the Stirling approximation

$$\log f(i)\simeq ni\log 2 -\frac i2\log(\frac 12n\pi)-i\log i+i-\frac 12\log(2\pi i)-\frac{i(i-n/2)^2}{n/2}$$

These terms are all negligable compared to the first and last, so

$$\log f(i)\simeq ni\log 2 -\frac{i(i-n/2)^2}{n/2}$$

$$=-\frac 2ni^3+2i^2+(\log2-\frac{1}2)ni$$

Therefore

$$\frac{d\log f(i)}{di}\simeq-\frac 6ni^2+4i+(\log 2-\frac 12)n$$

With roots

$$i=\frac{-4\pm\sqrt{16+24(\log 2-\frac 12)}}{-12/n}\simeq-0.0452n\text{ and }0.712n$$

The first is a minimum (and outside the sensible range) but the second is a maximum. Let $\alpha\simeq0.712n$ be this maximum.

So using our above approximation

$$\log f(\alpha)\simeq [-2\times 0.712^3+2\times 0.712^2+(\log2-\frac{1}2)\times 0.712]n^2\simeq0.430n^2$$

So bounding $\sum_i f(i)$ below by its largest term gives an approximation of about $e^{0.430n^2}$, which is in line with Claude Leibovici's empirical results.

This isn't a rigorous lower bound. The main problem is that $\alpha$ isn't an integer, and so $f(i)$ might not actually attain this maximum. Since $\alpha$ is within $\frac 12$ of an integer you can fix this by evaluating the second derivative of $\log f$ at $\alpha$ an use this to approximate $f(\alpha\pm\frac 12)$.

Solution 2:

This is not an answer since based on numerical simulation.

I wonder if any closed form could be found for $$S_n=\sum _{i=0}^n \binom{\binom{n}{i}}{i}$$ "Playing" with these huge numbers, what I noticed is that $\log(S_n)$ seems to follow a power law $a n^b$ and a quick and dirty curve fit gave $$\log(S_n)\approx 0.291338\, n^{2.06202}$$ ($R^2=0.999996$). This was done for $(1\leq n\leq 200)$ (notice that $S_{200}\approx 1.33 \times 10^{7018}$).

May be, this could give you some ideas.

Edit

I have been able to push the calculations up to $n=500$ (notice that $S_{500}\approx 1.31 \times 10^{45193}$) and what was obtained is $$\log(S_n)\approx 0.343341 n^{2.03113}$$ Intermediate calculations seem to show that the exponent tends to $2$ (but, not sure !!).

If we impose the power to be equal to $2$, the regression gives $$\log(S_n)\approx 0.414067 n^2$$ which is extremely close to Oscar Cunningham's result.

Edit

Inspired by Oscar Cunningham's very interesting answer, I computed rigorously the value of $i$ which maximizes the expression. The results are given below $$\left( \begin{array}{cc} n & i \\ 100 & 69 \\ 200 & 139 \\ 300 & 210 \\ 400 & 280 \\ 500 & 350 \\ 600 & 420 \\ 700 & 491 \\ 800 & 561 \\ 900 & 631 \\ 1000 & 702 \end{array} \right)$$

which is almost exactly $i=0.7 n$. Hence, the beauty of Oscar Cunningham's approximations !

Edit

Concerning $$T_n=\sum_{i=0}^n\binom{\binom{{\binom{n}{i}}}{i}}{i}$$ the same empirical approach leads to $$\log(T_n)\approx0.191665 n^{3.08625}$$ or, rounding the exponent,$$\log(T_n)\approx0.292268 n^{3}$$ The calculations were done up to $n=150$. Please notice that $T_{150}\approx 1.10\times 10^{432014}$

Solution 3:

I tried to add this as a comment but my credit was not enough. One direction of thought would be to use the following lower-bound multiple times (two or three times): $${n \choose k} \geq \left(\frac{n}{k}\right)^k$$ This would give you a good lower bound.