What is the determinant of the Pascal matrix $M_{ij} = \binom{2j+1}{i}$? For $0\le i,j\le N-1$, define $M_{ij} = \binom{2j+1}{i}$. For example, with $N=6$, we have
$$M_6=\left(\begin{array}{cccccc}1&1&1&1&1&1\\1&3&5&7&9&11\\0&3&10&21&36&55\\0&1&10&35&84&165\\0&0&5&35&126&330\\0&0&1&21&126&462\\\end{array}\right)$$
For the first few $N$s, I have $\det(M_2)=2$, $\det(M_3)=8$, $\det(M_4)=64$, $\det(M_5)=1024$, $\det(M_6)=32768$, so it is easy to conjecture
$$\det(M_N) = 2^{\binom{n}{2}}$$
This would suggest an induction approach, perhaps similar to the one proposed by Marc in this question. If the same approach worked in this case, we could apply some elimination matrices to reduce $M_N$ to something of the form
$$M_N=\left(\begin{array}{cc} 1 & 0 \\ 0 & 2M_{N-1}\end{array}\right)$$
at which point induction would finish the proof. However, the elimination matrices required to obtain this reduction are not as easy to find given that the elements of the matrix satisfy the recursion
$$M_{ij}=M_{i,j-1}+2M_{i-1,j-1}+M_{i-2,j-1}$$
where the last term is the one which causes most of the problems. Another idea would be to try to row reduce $M_N$ to a lower triangular matrix. For instance, with $N=6$, we would have:
$$M_6 \to \left(\begin{array}{cccccc}1&1&1&1&1&1\\0&2&4&6&8&10\\0&0&4&12&24&40\\0&0&0&8&32&80\\0&0&0&0&16&80\\0&0&0&0&0&32\\\end{array}\right)$$
from which the result is readily apparent. Dividing the $n$th row by $2^n$ reveals a Pascal matrix, so I was hoping one could transform the Pascal matrix to only include its odd-numbered columns. However, I have not been able to come up with the required manipulations. Is there something trivial I am missing?
 A: Inspired by Muse_China's comments under my question, we can define $U_{ij} = 2^i \binom{j}{i}$, which factors as $\text{diag}(1,2,2^2,\cdots, 2^{N-1})P_N$ where $P_N = \binom{j}{i}$ is the $N\times N$ Pascal matrix with inverse $P_N^{-1} = (-1)^{i+j}\binom{j}{i}$. It follows that $U_{ij}^{-1} = (-1)^{i+j}2^{-j}\binom{j}{i}$. If $U$ were the upper triangular factor in the LU decomposition of $M$, we must have $L=MU^{-1}$, so we must show $L$ is lower triangular and has $1$'s on the diagonal. Therefore, compute
$$\begin{align}
L_{ij} &= \sum_{k=0}^{N-1} M_{ik}U_{kj}^{-1} = \sum_{k=0}^{N-1}(-1)^{k+j}2^{-j} \binom{2k+1}{i}\binom{j}{k}
    \\
    &=(-2)^{-j}\sum_{k=0}^{j}(-1)^{k} \binom{2k+1}{i}\binom{j}{k}
\end{align}
$$
Introduce the "coefficient of" operator $[x^i]$ as $[x^i]\left(\sum_{j=0}^N a_jx^j\right)=a_i$ which is evidently linear and use it to re-write the $\binom{2k+1}i$ term above as $[x^i](1+x)^{2k+1}$. This simplifies the expression for $L$ to
$$
\begin{align}
L_{ij} &= (-2)^{-j}[x^i]\sum_{k=0}^{j}(-1)^{k} (1+x)^{2k+1}\binom{j}{k}
\\
&=(-2)^{-j}[x^i](1+x)\sum_{k=0}^{j}(-1)^{k} (1+x)^{2k}\binom{j}{k}
\\
&=(-2)^{-j}[x^i](1+x)(1-(1+x)^2)^j=2^{-j}[x^i](1+x)x^j(2+x)^j
\\
&=2^{-j}[x^{i-j}](1+x)(2+x)^j
\end{align}
$$
In particular, if $j> i$, the coefficient of operator picks up a $0$, and when $i=j$, it is clear that $[x^0](1+x)(2+x)^j=2^j$, and so $\det(L)=1$ and $\det(M_n)=\det(U)=2^{\binom{n}{2}}$.
A: First, consider the $LU$ decomposition of the Pascal matrix $M=LU$, where $L$ is a lower-triangular matrix and $U$ is an upper-triangular matrix. Inspired by the OP's work, we set $U_{ij} = 2^i \binom j i$. This proof uses two useful lemmas in Donald Knuth's book The Art of Computer Programming (TAOCP).
$\textbf{Lemma 1}$: Let $j$ be a positive integer and $b_0, b_1,...,b_j$ be real numbers. Then
$\sum\limits_{k=0}^j (-1)^{j+k} \binom j k (\sum\limits_{i=0}^j b_ik^i) = j!b_j$.
Proof of Lemma 1 is easy. We can recursively consider the binomial sum with respect to $i$:
$\sum\limits_{k=0}^j (-1)^{j+k} \binom j k \Pi_{t=0}^{i-1}(k - m)$
and show that
$\sum\limits_{k=0}^j (-1)^{j+k} \binom j k k^i = \begin{cases}
        0, & i<j;\\
        j!, & i=j.\\
        \end{cases} $
$\textbf{Lemma 2}$: Let $i, j, k$ be natural integers and $j \geq i$, then $\sum\limits_{k}(-1)^{i+k}\binom k i \binom j k = \delta_{ij}$. $\delta_{ij}$ is the well known Kronecker symbol which is $1$ if $i = j$ and $0$ if $i \neq j$.
$\textbf{Proof to Lemma 2}$:
First, $\sum\limits_k (-1)^{i+k} \binom k i \binom j k = (-1)^{i-j}\sum\limits_k(-1)^{j+k}\binom k i \binom j k$.
Now, we treat $\binom k i$ as a polynomial of $k$. The $\binom k i$ refers to $\sum\limits_{i=0}^j b_ik^i$ in Lemma 1. If $i < j$, then the coefficient of $k^j$ is $0$. Otherwise, if $i = j$, the coefficient of $k^j$ is $\frac{1}{j!}$. Therefore, according to Lemma 1, $\sum\limits_k (-1)^{i+k} \binom k i \binom j k = (-1)^{i-j} j! (\text{Coefficient of}\quad k^j \quad\text{in the polynomial} \quad \binom k i) = \delta_{ij}$.
$\textbf{Proof of Lemma 2 ends.}$
Following Lemma 2, we get $(U^{-1})_{ij} = (-1)^{i+j}2^{-j}\binom j i$. To be honest, I calculate $U^{-1}$ using Mathematica Pro 12 before proving it.
The next step is to calculate $MU^{-1}$. We have:
$L_{ij} = (MU^{-1})_{ij} = \sum\limits_{k}M_{ik}(U^{-1})_{kj} = \sum\limits_{k}(-1)^{j+k}2^{-j}\binom {2k+1} {i}\binom j k$. (1)
Here, we want to show that $L$ is a lower-triangular matrix with all its diagonal elements being $1$, i.e.,
$L_{ij} = \begin{cases}
        0, & i<j;\\
        1, & i=j.\\
        \end{cases}$ (2)
To prove (2), very similar to the proof of Lemma 2, we treat the binomial coefficient $\binom {2k+1} i$ in Eq. (1) as a polynomial of $k$. We treat the variable $j$ in Eq. (1) the same as Lemma 1. For the case where $i=j$, the coefficient of $k_j$ is $\frac{2^j}{j!}$. For the case where $i < j$, the coefficient of $k_j$ is $0$. Therefore, Eq. (2) is true and $L=MU^{-1}$ is a lower-triangular matrix with all its diagonal elements being $1$, hence $det(L) = 1$.
Finally, $\det(M) = \det(U) = 2^{\binom n 2}$.
