(Note: The matrix elements are indexed from $0$. To avoid confusion, I will not index into a matrix without brackets)

Here is a naive approach to this problem, without hindsight of the already-derived formula.

Lemma:
If $M \in \mathbb F^{n \times n}$ is an invertible matrix and $(\alpha_i),(\beta_i)$ are non-zero elements of $\mathbb F$, then the matrix formed by $$N := \left[(M)_{i,j}\alpha_i\beta_j\right]$$
is invertible, with its inverse given by
$$N^{-1} = \left[(M^{-1})_{i,j}\beta_i^{-1}\alpha_j^{-1}\right]$$

Let $H_n$ be the $n$-th Hilbert matrix, given by
$$ H_n = \left[\frac1{i+j+1}\right]_{i,j}
$$
Then $H_n$ is invertible and every element of $H_n^{-1}$ is an integer.

*Proof:* The $H_n$s are nested within each other:
$$ H_{n+1} = \begin{bmatrix} H_n & u \\ u^\intercal & 1/(2n+1)\end{bmatrix}
$$
Define $V_n := H_n - (2n+1)uu^\intercal$. Then
$$\begin{align*}
V_n &= \left[\frac1{i+j+1} - \frac{2n+1}{(n+1+i)(n+1+j)}\right] \\
&= \left[\frac{(n-i)(n-j)}{(i+j+1)(n+1+i)(n+1+j)}\right] \\
&= \left[(H_n)_{i,j} \frac{n -i}{n+1+i} \frac{n-j}{n+1+j}\right]
\end{align*}$$
It is well-known that if $V_n$ is invertible, then so is $H_{n+1}$, but the invertibility of $V_n$ is intrinsically linked to $H_n$, so an inductive argument gives that $H_n$ is invertible.

The inverse of $H_{n+1}$ is given by Blockwise inversion formula:
$$ H_{n+1}^{-1} = \begin{bmatrix}
V_n^{-1} & -(2n+1)V_n^{-1}u \\ -(2n+1)u^\intercal V_n^{-1} & (2n+1) + (2n+1)^2u^\intercal V_n^{-1} u\end{bmatrix}
$$
By the Lemma above, the inverse of $V_n$ is given by
$$ V_n^{-1} = \left[(H_n^{-1}) \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \right]
$$
Since $V_n^{-1}$ is a constituent of $H_{n+1}$, this can be used to telescope the entries of $H_n^{-1}$.

By the symmetry of $H_n,V_n,H_n^{-1}$, it suffices to consider the upper triangular portion of $H_n$. We can see that eventually a "interior" element of $H_n^{-1}$ "lands" on an edge element of some $H_n^{-1}$: Let $i,j<n$ with $i \leq j$. Then
$$\begin{align*}
(H_{n+1}^{-1})_{i,j} &= (V_n^{-1})_{i,j}
= (H_{j+1}^{-1})_{i,j} \frac{(2j+2)(i+j+2)}{1(j+1-i)} \cdots \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \\
&= (H_{j+1}^{-1})_{i,j} \frac{(n+1+i)!(n+1+j)!}{(2j+1)!(i+j+1)!} \frac{(j-i)!}{(n-i)!(n-j)!} \\
&= (H_{j+1}^{-1})_{i,j} \frac{(j-i)!}{(2j+1)!(i+j+1)!} \frac{(n+1+i)!(n+1+j)!}{(n-i)!(n-j)!(2i+1)!(2j+1)!} (2i+1)!(2j+1)! \\
&= (H_{j+1}^{-1})_{i,j} \frac{(j-i)!(2i+1)!}{(i+j+1)!} \binom{n+1+i}{n-i}\binom{n+1+j}{n-j} \\
&= (H_{j+1}^{-1})_{i,j} \frac{1}{\binom{i+j+1}{2i+1}} \binom{n+1+i}{n-i}\binom{n+1+j}{n-j}
\end{align*}$$
This is a very strong hint on what the inductive hypothesis should be.

**Inductive Hypothesis** P(n):

Every element of $H_n^{-1}$ is an integer, and $$\binom{n+i}{n-1-i}\binom{n+j}{n-1-j} \mid (H_n^{-1})_{i,j}$$
where $i,j \in \{0,\dots,n-1\}$.

Define the matrix
$$ A_n := \left[\frac{(H_n^{-1})_{i,j}}{\binom{n+i}{n-1-i} \binom{n+j}{n-1-j}}\right]_{i,j}
$$
$P(n)$ is just the statement that $A_n$ has integer entries. Evidently $P(1)$ holds. Suppose $P(n)$ holds for some $n$. We shall examine the validity of $P(n+1)$.

There are three cases:

- Suppose $i,j < n$. This corresponds to a "interior" element $(H_{n+1}^{-1})_{i,j}$ of $H_{n+1}^{-1}$.

We have that
$$\begin{align*}
(H_{n+1}^{-1})_{i,j} &= (V_n^{-1})_{i,j} = (H_n^{-1})_{i,j} \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \\
&= (A_n)_{i,j} \binom{n+i}{n-1-i}\binom{n+j}{n-1-j} \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \\
&= (A_n)_{i,j} \binom{n+1+i}{n-i} \binom{n+1+j}{n-j}
\end{align*}$$
Establishing the interior case. (It can also be inferred from this equation that $A_n$'s are nested within each other.)

The edge case: Consider the edge $-(2n+1)V_n^{-1}u$. Let $i \in \{0,\dots,n-1\}$ The $i$th element $(H_{n+1}^{-1})_{i,n}$ on the edge is given by the dot product
$$\begin{align*}
-(2n+1)(V_n^{-1}u)_i
&= -(2n+1) \sum_{j=0}^{n-1} (V_n^{-1})_{i,j} (u)_j \\
&= -(2n+1) \sum_{j=0}^{n-1} (H_n^{-1})_{i,j} \frac{(n+1+i)(n+1+j)}{(n-i)(n-j)} \frac1{n+1+j} \\
&= -\frac{(n+1+i)(2n+1)}{n-i} \sum_{j=0}^{n-1} (H_n^{-1})_{i,j} \frac1{n-j} \\
&= -\frac{(n+1+i)(2n+1)}{n-i} \sum_{j=0}^{n-1} (A_n)_{i,j} \binom{n+i}{n-1-i}\binom{n+j}{n-1-j} \frac1{n-j} \\
&= -\frac{n+1+i}{n-i}\binom{n+i}{n-1-i} \sum_{j=0}^{n-1} (A_n)_{i,j} \frac{2n+1}{n-j} \binom{n+j}{n-1-j}\\
\end{align*}$$
Here people proved that the multiplier in the sum is an integer, so it remains to show that
$$ \frac{n+1+i}{n-i}\binom{n+i}{n-1-i} = \binom{n+i+1}{n-i}
= \binom{n+i+1}{n-i}\binom{n+n+1}{n-n}
$$
is also an integer.

The corner element $(H_{n+1}^{-1})_{n,n}$ is given by the quadratic form:
$$\begin{align*}
(H_{n+1}^{-1})_{n,n} - (2n+1)
&= (2n+1)^2 \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} \frac{(H_n^{-1})_{i,j}}{(n-i)(n-j)} \\
&= \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} (A_n)_{i,j} \frac{(2n+1)(2n+1)}{(n-i)(n-j)}\binom{n+i}{n-1-i}\binom{n+j}{n-1-j}
\end{align*}$$
The last sum is a sum integers, and hence an integer. Trivially it holds that
$$ \binom{n+1+n}{n-n}\binom{n+1+n}{n-n} \mid (H_{n+1}^{-1})_{n,n}
$$
With all three cases established, the proof is complete by induction.

The Art of Computer Programming. $\endgroup$ – Suvrit Nov 28 '10 at 17:20