Product of binomial coefficient and fraction is integer

While deriving a elementary argument for the inverse of the Hilbert Matrix, I encountered the following quantity

If $n \in \mathbb Z_+$ and $i \in \{0,\dots,n-1\}$, then $$\frac{2n+1}{n-i} \binom{n+i}{n-1-i} = \frac{2n+1}{2i+1} \binom{n+i}{n-i}$$ is an integer.

Numerical evidence seems to suggest that it is true (verified for $n$ up to $1024$). But there are several subtleties:

1. If the $2n+1$ coefficient is removed, this statement is no longer true.
2. It might be tempting to separate the binomial coefficient into two using the Pascal Triangle: $$\binom{n+i}{n-1-i} = \binom{n-1+i}{n-2-i} + \binom{n-1+i}{n-1-i}$$ but each component after separating is not an integer.
3. By the substitution $n + i = a,n - i = b$, $$\frac{2n+1}{2i+1} \binom{n+i}{n-i} = \frac{a+b+1}{a-b-1} \binom{a}{b}$$
• Your integer is $\dbinom{n+i}{2i} + 2 \dbinom{n+i}{2i+1}$. – darij grinberg Jan 27 '18 at 0:50

1 Answer

Recalling the binomial identity $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$ we obtain \begin{align*} \color{blue}{\frac{2n+1}{n-i}\binom{n+i}{n-i-1}}&=\frac{(n-i)+(n+i+1)}{n-i}\binom{n+i}{n-i-1}\\ &=\left(1+\frac{n+i+1}{n-i}\right)\binom{n+i}{n-i-1}\\ &\color{blue}{=\binom{n+i}{n-i-1}+\binom{n+i+1}{n-i}\in\mathbb{Z}} \end{align*}