Why does the inverse of the Hilbert matrix have integer entries?

Let $A$ be the $n\times n$ matrix given by

$$A_{ij}=\frac{1}{i + j - 1}$$

Show that $A$ is invertible and that the inverse has integer entries.

I was able to show that $A$ is invertible. How do I show that $A^{-1}$ has integer entries?

This matrix is called the Hilbert matrix. The problem appears as exercise 12 in section 1.6 of Hoffman and Kunze's Linear Algebra (2nd edition).

Be wise, generalize (c)

I think the nicest way to answer this question is the direct computation of the inverse - however, for a more general matrix including the Hilbert matrix as a special case. The corresponding formulas have very transparent structure and nontrivial further generalizations.

The matrix $A$ is a particular case of the so-called Cauchy matrix with elements $$A_{ij}=\frac{1}{x_i-y_j},\qquad i,j=1,\ldots, N.$$ Namely, in the Hilbert case we can take $$x_i=i-\frac{1}{2},\qquad y_i=-i+\frac12.$$ The determinant of $A$ is given in the general case by $$\mathrm{det}\,A=\frac{\prod_{1\leq i<j\leq N}(x_i-x_j)(y_j-y_i)}{\prod_{1\leq i,j\leq N}(x_i-y_j)}.\tag{1}$$ Up to an easily computable constant prefactor, the structure of (1) follows from the observation that $\mathrm{det}\,A$ vanishes whenever there is a pair of coinciding $x$'s or $y$'s. (In the latter case $A$ contains a pair of coinciding raws/columns). For our $x$'s and $y$'s the determinant is clearly non-zero, hence $A$ is invertible.

One can also easily find the inverse $A^{-1}$, since the matrix obtained from a Cauchy matrix by deleting one row and one column is also of Cauchy type, with one $x$ and one $y$ less. Taking the ratio of the corresponding two determinants and using (1), most of the factors cancel out and one obtains \begin{align} A_{mn}^{-1}=\frac{1}{y_m-x_n}\frac{\prod_{1\leq i\leq N}(x_n-y_i)\cdot\prod_{1\leq i\leq N}(y_m-x_i)}{\prod_{i\neq n}(x_n-x_i)\cdot\prod_{i\neq m}(y_m-y_i)}.\tag{2} \end{align}

For our particular $x$'s and $y$'s, the formula (2) reduces to \begin{align} A_{mn}^{-1}&=\frac{(-1)^{m+n}}{m+n-1}\frac{\frac{(n+N-1)!}{(n-1)!}\cdot \frac{(m+N-1)!}{(m-1)!}}{(n-1)!(N-n)!\cdot(m-1)!(N-m)!}=\\ &=(-1)^{m+n}(m+n-1){n+N-1 \choose N-m}{m+N-1 \choose N-n}{m+n-2\choose m-1}^2. \end{align} The last expression is clearly integer. $\blacksquare$