Certain matrices of interesting determinant Let $M_n$ be the $n\times n$ matrix with entries
$$\binom{i}{2j}+\binom{j}{2i}, \qquad \text{for $1\leq i,j\leq n$}.$$

QUESTION. Is this true? There is some evidence. The determinant $\det(M_{2n+1})=0$ and
  $$\det(M_{2n})=(-1)^n\binom{2n}n^22^{n(n-3)}.$$

 A: As a follow-up on Fedor's wonderful proof, I would like to pen down just a comment. 
Let's replace $c_j+j$ by $u_j$ and treat $N$ as an indeterminate. Then, for non-negative integers $a$ and $b$, we have the determinantal evaluation
$$\det\left(\binom{N+i+a}{u_{j+b}}\right)_{i,j=0}^{n-1}
=\prod_{i=0}^{n-1}\frac{(N+i+a)!}{(N+n-a-1)!}\binom{N+n+a-1}{u_{i+b}}\prod_{i<j}^{0,n-1}(u_{j+b}-u_{i+b}).$$
The proof follows from the method of condensation; see Desnanot–Jacobi identity.
Remark. The introduction (or generalization) of the parameters $a$ and $b$ is what makes above-mentioned method work, effectively.
A: Noam Elkies in the comments reduces the problem to the identity $$\det\left(\binom{(n+1)+i}{2j+2}\right)_{i,j=0}^{n-1}=\binom{2n}n2^{n(n-3)/2}.$$ In general the determinant $\binom{N+i}{c_j+j}$, $i,j=0,\dots,n-1$ for integers $0\leqslant c_0\leqslant c_1\leqslant \dots \leqslant c_{n-1}\leqslant N$ may be calculated by the following trick. 
Consider the Young diagrams $\lambda,\mu$ with rows length $c_0\leqslant c_1\leqslant \dots \leqslant c_{n-1}$ and $N,N,\dots,N$ ($n$ rows in total) respectively. Count the skew Young tableaux of the shape $\mu\setminus \lambda$. On one hand, the number of such tableaux is known (see Okounkov, A., Olshanski, G.: Shifted Schur functions. St. Petersburg Math. J. 9(2), 73–146 (1997), Theorem 8.1) to be equal to $$\frac{(N\cdot n-\sum c_i)!}{\prod_{i=0}^{n-1} (N+i)!}\cdot \prod_{i=0}^{n-1} (c_i+i)!\cdot \det\left(\binom{N+i}{c_j+j}\right)_{i,j=0}^{n-1}.$$
On the other hand, it is the same as the number of usual Young tableaux of the shape $(N-c_0,\dots,N-c_{n-1})$, which may be evaluated by Hook Length Formula as
$$
\frac{(N\cdot n-\sum c_i)!}{\prod_{i=0}^{n-1} (N-c_{n-i-1}+i)!}\cdot \prod_{i<j} (c_j+j-c_i-i).
$$
Therefore 
$$
\det\left(\binom{N+i}{c_j+j}\right)_{i,j=0}^{n-1}=\\
\prod_{i=0}^{n-1}\frac{(N+i)!}{(c_i+i)!(N-c_{n-i-1}+i)!}\cdot \prod_{i<j} (c_j+j-c_i-i).\quad (*)
$$
It remains to substitute $N=n+1$ and $c_i=i+2$.
We get $$\prod_{i<j} (c_j+j-c_i-i)=2^{n(n-1)/2}\prod_{i<j}(j-i)=\prod_{i<j} (c_j+j-c_i-i)=2^{n(n-1)/2}\prod_{i=0}^{n-1} i!$$
and $(*)$ rewrites as
$$
\det\left(\binom{(n+1)+i}{2j+2}\right)_{i,j=0}^{n-1}=
\frac{1!2!\dots (n-1)! (n+1)!\dots (2n)!}
{2!4!\dots (2n)! 2! 4!\dots (2n-2)!}2^{n(n-1)/2}.
$$
Replace $2!4!\dots (2n)!$ to $$2\cdot 1!\cdot 4\cdot 3!\cdot 6\cdot 5!\cdot \ldots\cdot (2n)\cdot(2n-1)!=\\=2^nn! 1!3!\dots (2n-1)!.$$ We get $\frac{(2n)!}{n!n!} 2^{n(n-3)/2}$
as supposed.
Remark: of course the above determinant is a polynomial in $N$, and if we replace $(N+i)!/(N-c_{n-i-1}+i)!$ in $(*)$ by $c_{n-i-1}! \binom{N+i}{c_{n-i-1}}$, the formula becomes true for arbitrary $N$, not necessarily positive integer.
