# Asymptotic approximation of the expression $\sum^{N}_{i=0}\log\Bigg[\binom{\binom{N+1}{i}}{t_i}\Bigg]$

I am wondering about the asymptotic approximation of the following expression: $$S=\sum^{N}_{i=0}\log\Bigg[\binom{\binom{N+1}{i}}{t_i}\Bigg]$$ where $$t_i=\binom{N}{i}-\binom{N-k}{i-k}+\binom{N-k}{i-1}$$ where $k$ is a positive integer. Also we have that $k\ll N$. Also for those binomials that have $i<k$ (namely negative) we count them as zero. I am trying to work out the approximation for $N \rightarrow \infty$.

• You've posted variants of this over the last few weeks, and no one's biting. I like asymptotics, but I won't attempt it because there are three variables. Even 2 can be very difficult and often one parameter has to take on a 'small,' 'mid' and 'large' case analysis. If you are summing over one of the three variables, it would be better to show the full problem and there's a ghost of a chance someone might be interested. – skbmoore Aug 29 '18 at 17:15
• Why are you wondering about this sum? In what context does the sum of a logarithm of a binomial coefficient of binomial coefficients arise? – Antonio Vargas Aug 29 '18 at 19:08
• @skbmoore I know that this looks like a horrendous sum to be solved, hence I posted variations of it. The sum is over $i$ which appears in many terms unfortunately. The only constant is $k$ which can be fixed to a +ve integer bigger than 1 if it is of any help. I think the real issue is how to simplify the $t_i$ first, I tried various ways, to write of as leading Stirling approximation / in terms of factorials yet those are not so helpful. The expression $S$ is indeed the original problems, previous posts were my attempt to simplify it. – William Aug 30 '18 at 8:29
• @AntonioVargas It is a counting problem, this problem came up when I want to calculate some information content. – William Aug 30 '18 at 8:31
• An approximation for $k=2$ is the following: let $\eps=1/4(\sqrt{(1+4/n)}-1)$ and $w(u)=u(2u+1)-1/(2n).$ Call your sum, but with $n=N+1, S(n).$ Then $$S(n)\sim -2^n \sqrt{\frac{2n}{\pi}} \int_\eps^1/2 \exp{(-2nu^2)}(w(u)\log(w(u)+(1-w(u))\log(1-w(u))\,du$$ Can't make it rigorous and I shudder to think what happens for variable $k.$ The integral rep is about 1% accurate for $n=100.$ – skbmoore Aug 30 '18 at 22:03

Here are the asymptotics and a method for $k=1$ through $k=4.$ Unfortunately there does not appear to be a simple pattern developing. Also, I'm using $n=N-1.$

$\textbf{k=1}$ $$S_1:=\sum_{m=0}^n \log{ \Big[ \binom{\binom{n}{m}}{ \binom{n-1}{m}} }\Big] = \sum_{m=1}^{n-1} \log{\Big[ \binom{\binom{n}{m}}{ \binom{n}{m}(1-m/n) } }\Big]$$ The sum starting and ending value has been shifted by 1 towards the center because those end values within the square bracket are 1, and $\log(1)=0.$ Use the 'central value' estimate for the binomials, $$\binom{n}{m} \sim \binom{n}{n/2} e^{-\tfrac{2}{n}\big(\tfrac{n}{2}-m\big)^2 } .$$ Note: I haven't justified that this is sufficient other than numerically. Use the asymptotic expansion for $\log{\Gamma(1+x)},$ $$\log{\Gamma(1+x)} \sim x\log{(x/e)} + \log{(\sqrt{2\pi x})} + ...$$ Only the first term of the previous will be used when estimating $S_1.$ In thefollowing let $a=\binom{n}{m}$ and $y=m/n.$ Then $$S_1 \sim\binom{n}{n/2} \sum_{m=1}^{n-1} e^{-\tfrac{2}{n}\big(\tfrac{n}{2}-m\big)^2 } \big\{ \log{(a/e)}-(1-y)\log{(a\,(1-y)/e)}-y\log{(a \,y /e)} \big\}$$ The $\{\cdot\}$ simplifies so that it is independent of $a,$ $$\{\cdot\} = H(y):=-\big(y\,\log{y} + (1-y)\log{(1-y)} \big)$$ Therefore $$S_1 \sim\binom{n}{n/2} \sum_{m=1}^{n-1} e^{-2n\big(\tfrac{m}{n}-\tfrac{1}{2}\big)^2 } H(m/n)$$ In the limit that $n$ is large, interpret the previous expression as a Riemann integral: $$S_1\sim\binom{n}{n/2} \, n\, \int_0^1 e^{-2n\big(u-\tfrac{1}{2}\big)^2 } H(u) \,du = \binom{n}{n/2} \, n\, \int_{-1/2}^{1/2} e^{-2n\, u^2} H(w_1(u)) \,du$$ where $w_1(u) = 1/2 + u.$ One may expand $H(w_1(u))$ in a power series about $u=0,$ extend the limits on the integral to $\pm \infty$ so to use Gaussian integrals to get a close form, and expand the leading binomial and $n$ factor to finally get $$S_1 \sim 2^n\big(\log{2} - \frac{\log{2}+2}{4n} + o(1/n) \big)$$
For the other results, a polynomial associated with the index $k$ has been determined. That is, the results will be expressed as $$\quad (A) \quad S_k\sim\binom{n}{n/2} \, n\, \int_{-1/2}^{1/2} e^{-2n\, u^2} H(w_k(u)) \,du$$ $\textbf{k=2:} \quad w_2=\frac{1}{2}+\frac{3}{2}u - 2 u^3$

$\textbf{k=3:} \quad w_2=\frac{1}{2}+\frac{3}{2}u - 2 u^3$

$\textbf{k=4:} \quad w_2=\frac{1}{2}+\frac{11}{8}u - u^3 - 2u^5$

That the $k=2$ is the same as the $k=3$ case is not a typo. There are three sources of error so far unquantified: the central binomial approximation, the dropping of subsequent terms in the $\log{\Gamma}$ expansion, and the error in going from a sum to the integral. Another error will appear when $k$ gets appreciably large with respect to $n:$ One continues to 'pinch' the ends of the integral and the simple Riemann integrals presented will need corrections. This approach may completely fall apart if $k = \alpha n$, with, say, $\alpha \ge 1/10.$

The following is a comparison of values as calculated by the original definition, and by eq. (A). Multiply the entry by the scientific notation designator indicated in the table.

$$\begin{array}{c|lcr} k & S_{16} & S_{16}^{A} & S_{100} & S_{100}^{A} \\ {} & \quad \cdot 10^4 & & & \cdot 10^{29} \\ \hline 1 & 4.325 & 4.263 & 8.723 & 8.701 \\ 2 & 4.040 & 4.045 & 8.642 & 8.624 \\ 3 & 4.038 & 4.045 & 8.642 & 8.624 \\ 4 & 4.088 & 4.098 & 8.666 & 8.645 \end{array}$$ To me it appears that the values depend weakly on $k$ and an insistence that the asymptotic formula is accurate for these distinctions means that those errors mentioned previously need to be dealt with.