Let $n \in\mathbb{N}$ and $A=(a_{ij})$ where \begin{equation}a_{ij}=\binom{i+j}{i}\end{equation} for $0\leq i,j \leq n$. Show that $A$ has an inverse and that every element of $A^{-1}$ is an integer.
I have shown that this $n\times n$ matrix is symmetric since, \begin{equation} \binom{i+j}{i}=\binom{i+j}{j} \end{equation} in order to try to get a nonzero determinant. But i'm stuck in this step, suggestions would be appreciated.
On
If you take a particular case (say $n=5$) and you consider the LDL or Cholesky decomposition of this matrix you notice something very interesting: ( WA link).
So one should try to prove that our matrix $A$ is the product $$A = L \cdot L^t$$ where $L = (\binom{i}{j})_{0\le i,j \le n}$.This translates into the equalities: $$\sum_k\binom{i}{k} \binom{j}{k} = \sum_k\binom{i}{k} \binom{j}{j-k}= \binom{i+j}{j}$$
Note that $L$ is lower triangular with $1$ on the diagonal, so invertible. In fact, its inverse can be explicitely given $$L^{-1} = ((-1)^{i-k} \binom{i}{j})$$ One can prove a more general equality $$L^{a}\cdot L^{b}=L^{a+b}$$ where $L_{ij}^a =a^{i-j} \binom{i}{j}$.
So now we get $$A^{-1} = (L\cdot L^t)^{-1}= (L^{-1})^t \cdot L^{-1}$$ so clearly with integral elements, although I can't notice a particularly nice form for the entries.
Notice: matrices of the form $\binom{a+i+j}{j}$, or $\binom{a+i}{j}$, or $\binom{a-i}{j}$, or more generally, $\binom{a \pm i + b j}{j}$ also have nice LU decompositions. ($a$, $b$ parameters). The L part (the lower triangular part) is always $\binom{i}{j}$.
There's a usually useless formula for the matrix inverse in terms of cofactors. It's actually useful here. The elements $b_{ij}$ of the matrix inverse are explicitely given by:
$$b_{ij}=\frac{|C_{ij}|}{|A|},$$
where $C_{ij}$ is the cofactor matrix. Show by a method of your choice, such as induction, that $|A|=1$, for all $n$. Then the answer is clear because $|C_{ij}|$ is just a sum of integer products.