Approximation a sum involving log and binomial coefficient

Question

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$.

Answer 1

Let $B$ stand in for $\binom{N+1}{i}$, and assume $N$ is much bigger than 2. $B$ (when nonzero) ranges from $1$ to less than $2^N$, so $\log B$ can be found in the range $ (0,N)$. I'm ignoring a multiplicative constant here as I want to talk in qualitative terms about your sum; you can redo the argument with more care.

Your sum involves logarithms of binomial coefficients of B for differing values of $B$. Thus each of the $N+1$ terms in your sum is a value between 1 and $B$, which gives a rough upper bound of $2^{N+1}$ for the total. This is without taking the values $t_i$ in consideration.

Now note for each $i$ that $B= \binom{N}{i} + \binom{N}{i-1}$. We have that each term inside the log in your summands is majorized by the corresponding term $\binom{B}{\binom{N}{i-1}}$, and when $i$ is far from $N/2$, this is a value much smaller than $2^B$.

How far is far? That I don't know, but I imagine that when $i$ is about $\sqrt{N}$ away from $(N+1)/2$, the log term of your sum is so much smaller than the maximal term that it can be safely ignored. The largest term will be like log of the middle binomial coefficient for $B$, so its value will be less than something like $B - \log B$, and only the middle terms will matter, giving something like $2\sqrt{N}B$ for an upper bound on your sum.

Note that I am using rough estimates and intuition on the shape of the binomial distribution. Although I guarantee the quality of the estimates above, you need to crunch the numbers to come up with an accurate bound, which will look like my estimate above modulo some multiplicative factor. I cannot imagine a simplification that would lead to a closed form or a better bound. The major trick (now that I see this version) is to note that $t_i$ differs from $B$ by a relatively small binomial coefficient, which gives that most of the terms (before log) are really small compared to the middle terms.

Gerhard "Throwing Out The Small Terms" Paseman, 2018.08.31.