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).
 A: 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$
