Showing  a matrix is negative definite [formerly Showing a sum is always positive] For each $d$, I have a matrix $M$ with values
$$
   M_{ij} = \begin{cases}
          \frac{4ij}{d} - \binom{2d}{d} & i \neq j & \\\\
          \frac{4i^2}{d} - \binom{2d}{d} - 
            \frac{\binom{2d}{d}}{\binom{d}{i}^{2}}  & i = j
        \end{cases}
$$
I want to show that, for every $d=2,3,\ldots$, the matrix is negative-definite. 
An elegant answer has been provided by fedja, without needing to look at the determinants
My approach is to compute the determinant of the upper left-square matrix of size $k$, for each $k=1,2,\ldots,d$. The value for this is
$$
D_k = (-1)^k\left[\frac{\binom{2d}{d}^k}{\prod_{i=1}^{k}\binom{d}{i}^2}\right]
\left[\sum_{j=1}^{k}\left(\binom{d}{j}^2 - \frac{4j^2\binom{d}{j}^2}{d\binom{2d}{d}}\right)
 - \frac{4}{d\binom{2d}{d}}
 \sum_{1 \leq i < j \leq k}(j-i)^2\binom{d}{i}^2\binom{d}{j}^2\right]
$$
Hence, $D_k$ has sign $(-1)^k$ if this expression is positive
$$
\sum_{j=1}^{k}\left(\binom{d}{j}^2 - \frac{4j^2\binom{d}{j}^2}{d\binom{2d}{d}}\right)
 - \frac{4}{d\binom{2d}{d}}
 \sum_{1 \leq i < j \leq k}(j-i)^2\binom{d}{i}^2\binom{d}{j}^2
$$
I can re-write this as
$$
\sum_{j=0}^{k}\binom{d}{j}^2 - \frac{2}{d\binom{2d}{d}}
     \sum_{0 \leq i,j \leq k}(j-i)^2\binom{d}{i}^2\binom{d}{j}^2\,,
$$
and, then, after observing that $\sum_{i=0}^{d}i\binom{d}{i}^2 = \frac{d}{2}\binom{2d}{d}$,
I can deduce that this will certainly be positive when the following sum is positive
$$\sum_{0 \leq i, j \leq k}(i-(j-i)^2){\binom{d}{i}}^2{\binom{d}{j}}^2$$
Any advice/techniques would be appreciated.
 A: 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$.
A: It's easier to prove the result about the matrix without resorting to determinants. What we need is the inequality
$$
\left(\sum_{i=0}^d 2ix_i\right)^2\le d{2d\choose d}\left(\sum_{i=0}^d x_i\right)^2
+d\sum_{i=0}^d \frac{{2d\choose d}}{{d\choose i}^2}x_i^2
$$
Now recall that $\sum_{i=0}^d (2i-d)^2{d\choose i}^2=\frac{d^2}{2d-1}{2d\choose d}$ (elementary computation with generating functions; should have some combinatorial proof as well) and that $(A+B)^2\le \frac{2d-1}dA^2+\frac{2d-1}{d-1}B^2$. Putting 
$$
A=\sum_{i=0}^d(2i-d)x_i\,,\qquad B=d\sum_{i=0}^d x_i
$$
we see that we can use Cauchy-Schwarz to get 
$$
A^2\le \frac{d^2}{2d-1}\sum_{i=0}^d \frac{{2d\choose d}}{{d\choose i}^2}x_i^2
$$
so we just need to check that $d^2\frac{2d-1}{d-1}\le d{2d\choose d}$ for $d\ge 2$, which is rather trivial.
