(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:

1. 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.)

2. 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.

3. 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)} \\ &= (2n+1)^2 \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*}$$ It is immediate that the last sum is a sum of a bunch of 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.

(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:

1. 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.)

2. 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.

3. 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.

(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]$$

$H_n$ is invertible and every element of $H_n^{-1}$ is an integer.

Let $H_n$ be the $n$-th Hilbert matrix, given by $$ H_n = \left[\frac1{i+j+1}\right]_{i,j} $$ It follows that 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:

1. 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.)

2. 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.

3. 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)} \\ &= (2n+1)^2 \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*}$$ It is immediate that the last sum is a sum of a bunch of 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.

(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:

1. 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.)

2. 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.

3. 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)} \\ &= (2n+1)^2 \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*}$$ It is immediate that the last sum is a sum of a bunch of 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.