co.combinatorics - Showing a matrix is negative definite [formerly Showing a sum is always positive]

Here is a sketch of a solution; the details would be tedious, but doable by someone with enough patience I think.

The point is that the terms with $i$ and $j$ both of the form $d/2 + O(sqrt{d})$ are so much larger than the others that they are the only ones that matter, unless of course $k$ is significantly less than $d/2$ in which case those terms are not present in the sum and then the terms that matter are the ones where $i$ and $j$ are very close to $k$. The rest of the terms are "error terms".

More precisely, for fixed $B$ and fixed $C>|B|$, and for $k ge d/2 - B sqrt{d}$, the sum of the terms with $|i-d/2| le C sqrt{d}$ and $|j-d/2| le C sqrt{d}$ can be approximated by using Stirling's formula to estimate the binomial coefficients (this amounts to replacing the double sum by a double integral involving the product of two copies of the square of the normal distribution). The result of this is that the double sum can be bounded below by a positive constant times $2^{4d}$, where the constant depends only on $B$.

On the other hand, still for $k$ in this range, bounding the absolute values of the rest of the terms in the sum (i.e., with $(i,j)$ outside that "central square") shows that they contribute a total whose absolute value is at most $epsilon 2^{4d}$ where $epsilon$ can be made arbitrarily small by taking $C$ large enough. So this proves that your sum $f(d,k)$ is positive for $k ge d/2 - B sqrt{d}$.

For smaller values of $k$, the same Stirling's approximation estimates apply. This time the largest terms are not as large as they were in the central square, but the strategy is the same: to show that the sum of the terms with $(i,j)$ outside a small neighborhood of $(k,k)$ are negligible compared to the sum of the terms inside the neighborhood, which can be estimated analytically. $square$

---

There may be some shortcuts that would save you some of the work involved above. For instance, Mathematica gave me a formula that I think is equivalent to
$$f(d,d) = frac{d(d-1)}{2(2d-1)} binom{2d}{d}^2,$$
which is certainly positive, so if one could show that for fixed $d$, the sequence of values $f(d,k)$ for $k=0,1,ldots,d$ is increasing up to a point and decreasing thereafter, that would suffice. Perhaps using the Stirling approximation you can show that $f(d,k)-f(d,k-1)>0$ for $k<d/2$, in which case you could avoid the last paragraph of the argument above dealing with small $k$.