Proving that $(k + 1) \mid \binom{n}{k}\binom{n+1}{k}$ for positive integers $n, k$ I've been playing around with some binomial coefficients and their divisibility, and I stumbled upon a relation that seems to hold, at least for $0 < k < n < 200$ (checked with Python): $$ (k + 1) \mid \binom{n}{k}\binom{n+1}{k}. $$
I initially thought that the following reasoning would work. Since $\binom{n}{k}$ has $k$ terms in the numerator, the only way that there is no multiple of $(k+1)$ in the numerator of $\binom{n}{k}$ is when $n \equiv -1 \pmod{k+1}$. But then $(k+1)\mid(n+1)$, so there is a multiple of $(k+1)$ in the numerator of $\binom{n+1}{k}$.
Unfortunately, I'm not sure if showing that there is a multiple of $(k+1)$ in the numerator of the expression is sufficient for all values of $k$. It definitely works when $(k+1)$ is prime, but if not, there is the possibility that the designated multiple of $(k+1)$ is canceled out by other terms in the denominator.
So: is there a way to patch up this argument, or could this statement be proven by entirely different means? (Bonus brownie points if there's a combinatorial argument.) Thanks!
 A: Here is a combinatorial proof I know I saw elsewhere on this site, but I am not able to find it again. Since
$$
\frac{1}{k+1}\binom{n}{k}\binom{n+1}{k}=\frac1{n+1}\binom{n+1}{k+1}\binom{n+1}{k}
$$
we can instead prove that $(n+1)|\binom{n+1}{k+1}\binom{n+1}{k}$. Consider the set of ordered pairs of the form
$$
(A,B),\;\;\text{where}\qquad A,B\subseteq \{0,1,\dots,n\},\qquad |A|=k,\;\;|B|=k+1
$$
The number of such ordered pairs is $\binom{n+1}{k+1}\binom{n+1}{k}$. We will partition all of these ordered pairs into groups of size $n+1$, which proves that $(n+1)|\binom{n+1}{k+1}\binom{n+1}{k}$. Specifically, the group associated with $(A,B)$ is
$$
\{(A,B),(A+1,B+1),(A+2,B+2),\dots,(A+n,B+n)\}
$$
where
$$
A+k:=\{a+k\pmod {n+1}:a\in A\}.
$$
To prove this works, you need to show that those $n+1$ sets are actually distinct, meaning the ordered pairs $(A+i,B+i)$ and $(A+j,B+j)$ are unequal whenever $i\neq j$ The proof of that relies on $k$ and $k+1$ being coprime.
A: You might want to find a combinatorial proof along the following lines:
\begin{align*}
\color{blue}{\frac{1}{k+1}\binom{n}{k}\binom{n+1}{k}}
&=\left(1-\frac{k}{k+1}\right)\binom{n}{k}\binom{n+1}{k}\\
&=\binom{n}{k}\binom{n+1}{k}-\frac{n+1}{k+1}\binom{n}{k}\binom{n}{k-1}\\
&\,\,\color{blue}{=\binom{n}{k}\binom{n+1}{k}-\binom{n+1}{k+1}\binom{n}{k-1}}
\end{align*}
