Proof that a certain fraction is always an integer Prove that $$\frac{(n+1)(n)^2(n-1)^2...(n-k+2)^2(n-k+1)}{(k+1)(k)^2(k-1)^2...(2)^2(1)}$$ is or is not an integer for $0\leq k \leq n$, where $k$ and $n$ are integer values.
This looks like $\frac{(n+1)!(n)!}{(n-k+1)(n-k)(k+1)!(k)!}$. The above statement is true for k=1 and k=2 as seen by observing modular residues. Not sure how to proceed.
I’m going to give the answer more or less as I worked through the problem, since these numbers turn out to be rather interesting; if you just want a quick and easy computational proof, skip to the end.
I rewrote it as
$$\frac{n!}{k!(n-k)!}\cdot\frac{(n+1)!}{(k+1)!(n-k+1)!}=\frac1{k+1}\binom{n}k\binom{n+1}k\,,\tag{1}$$
and calculated some values:
$$\begin{array}{c|cc}
n\backslash k&amp;0&amp;1&amp;2&amp;3&amp;4&amp;5\\\hline
0&amp;1\\
1&amp;1&amp;1\\
2&amp;1&amp;3&amp;1\\
3&amp;1&amp;6&amp;6&amp;1\\
4&amp;1&amp;10&amp;20&amp;10&amp;1\\
5&amp;1&amp;15&amp;50&amp;50&amp;15&amp;1
\end{array}$$
The row sums are familiar: $1,2,5,14,42,132$ are the Catalan numbers $C_{n+1}$. This does suggest that these numbers may be counting something. And if we look up the triangle in OEIS by searching on the sequence
$$1,1,1,1,3,1,1,6,6,1,1,10,20,10,1\,,$$
the very first return is A001263, the sequence of Narayana numbers, whose first FORMULA entry is an offset version of the righthand side of $(1)$. If the entry in row $n$, column $k$ of my table is $t(n,k)$, then $t(n,k)$ is the Narayana number $N(n+1,k+1)$ and is the number of Dyck paths of length $2(n+1)$ having exactly $k+1$ peaks. Thus, it must be an integer.
That $N(n,k)$ is the number of Dyck paths having exactly $k$ humps is not obvious; one proof can be found in this PDF. However, the FORMULA section of the OEIS entry also notes that
$$N(n,k)=\binom{n-1}{k-1}\binom{n+1}k-\binom{n}{k-1}\binom{n}k\,,$$
which suggests the following purely computational proof that the original expression is an integer:
$$\begin{align*}
&amp;\binom{n}k\binom{n+2}{k+1}-\binom{n+1}k\binom{n+1}{k+1}\\\\
&amp;\qquad=\frac{n!(n+2)!}{k!(k+1)!(n-k)!(n-k+1)!}-\frac{(n+1)!^2}{k!(k+1)!(n-k+1)!(n-k)!}\\\\
&amp;\qquad=\frac{n!(n+2)!-(n+1)!^2}{k!(k+1)!(n-k+1)!(n-k)!}\\\\
&amp;\qquad=\frac{(n+1)!^2\left(\frac{n+2}{n+1}-1\right)}{{k!(k+1)!(n-k+1)!(n-k)!}}\\\\
&amp;\qquad=\frac{n!(n+1)!}{{k!(k+1)!(n-k+1)!(n-k)!}}\,.
\end{align*}$$
Here the first expression is clearly an integer, and the last is easily seen to be equivalent to the original fraction.
$\frac{(n+1)!(n)!}{(n-k+1)(n-k)(k+1)!(k)!}$ not quite but close
$\frac{(n+1)(n)^2(n-1)^2...(n-k+2)^2(n-k+1)}{(k+1)(k)^2(k-1)^2...(2)^2(1)}=$
$\frac {(n+1)n(n-1)....(n-k+2)}{(k+1)k(k-1).....\cdot 1}\cdot \frac {n(n-1)....(n-k+1)}{k(k-1).....\cdot 1}=$
$\frac {(n+1)!}{(k+1)!(n-k-1)!}\cdot \frac {n!}{k!(n-k)!}$.
${n+1 \choose k+1}{n\choose k}$
You should know thatboth ${n+1 \choose k+1}$ and ${n\choose k}$ are both integers so their product is.
Combinitorially the number of way to pick $k$ objects from a collection of $n$ objects must be an integer (just do them one after another and counting them).  And if we try to calculate what that integer is we can prove it must be $\frac {n!}{k!(n-k)!}$ and so that must be an integer.
We can prove it algebraically be noting that every $m$ consecutive integers will have a multiple of $m$ so each $m = 1,2,3,....k$ will divide an integer in $n-k+1,....., n$.  so the product of $k!$ will divide the product of $(n-k+1)(n-k+2)...n$.
Okay... theres an issue that $m$ may divide a $n-j$ and $p$ may divide the same $n-j$ but we not have $mp$ dividing $n-j$.  But then the prime components must be split somewhere else.  (I've always found that very tedious.)  But combinitorially we know the result must be true.