Proof that a certain fraction is always an integer

Question

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.

Answer 1

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&0&1&2&3&4&5\\\hline 0&1\\ 1&1&1\\ 2&1&3&1\\ 3&1&6&6&1\\ 4&1&10&20&10&1\\ 5&1&15&50&50&15&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*} &\binom{n}k\binom{n+2}{k+1}-\binom{n+1}k\binom{n+1}{k+1}\\\\ &\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)!}\\\\ &\qquad=\frac{n!(n+2)!-(n+1)!^2}{k!(k+1)!(n-k+1)!(n-k)!}\\\\ &\qquad=\frac{(n+1)!^2\left(\frac{n+2}{n+1}-1\right)}{{k!(k+1)!(n-k+1)!(n-k)!}}\\\\ &\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.

Answer 2

Easy: it's $\large\color{#c00}{\frac{f_{n+1}f_n}{k+1}}$ for $f_n =\large {n\choose k}.\,$ $\,\color{#c00}{k\!+\!1}\mid \color{#0a0}{(n\!+\!1)f_n} = (k\!+\!1)\large {n+1\choose k+1}\,$ so $\,\color{#c00}{k\!+\!1\mid f_{n+1}f_n}\,$ by

Lemma $\ \forall n\!: \color{#0a0}{(n\!+\!1)f_n}\equiv 0\,\Rightarrow\, \forall n\!: f_{n+1}f_n\equiv 0,\ $ since

$\ \ \ \ \ f_{n+1}f_n \equiv \color{#0a0}{(n\!+\!2)f_{n+1}}f_n - \color{#0a0}{(n\!+\!1)f_n} f_{n+1} \equiv 0\ \ $ (all $\bmod \color{#c00}{k\!+\!1}\,$ for above)

Answer 3

Transplanted answer, from duplicate query that was subsequently closed. Actual (duplicate) query was:

For $n, k \in \mathbb{N}$ such that $n \geq k, $ how do I show that

$$\prod_{\alpha = 1}^{k}\alpha(\alpha + 1) \quad \text{always divides} \quad \prod_{\alpha = n - k + 1}^{n}\alpha(\alpha + 1) $$

---

---

Hint

Use Induction on Pascal's Triangle to demonstrate that $\binom{n}{k}$ is always an integer.

Then, demonstrate that the quotient equals $\binom{n}{k} \times \binom{n+1}{k+1}.$

Edit
I mistakenly thought that the RHS $\div$ LHS simplified to
$\binom{n}{k} \times \binom{n+1}{k+1}.$ This is wrong!

RHS $\div$ LHS $= \frac{1}{n-k+1} \times \binom{n}{k} \times \binom{n+1}{k+1} ~=~ \frac{1}{k+1} \times \binom{n}{k} \times \binom{n+1}{k}.$

Therefore, the problem reduces to either showing that

$(n-k+1)$ divides $\binom{n}{k} \times \binom{n+1}{k+1}$

or showing that

$(k+1)$ divides $\binom{n}{k} \times \binom{n+1}{k}.~~~$ This is what I will show.

---

Answer Repaired
For $x \in \mathbb{Z^+},$ and $p$ a prime,
let $V_p(x)$ denote the largest non-negative integer $y$ such that $p^y$ divides $x$.

Let $p$ be any prime factor of $(k+1)$, with $V_p(k+1) = a$.

I am going to show that $V_p\left[\binom{n}{k}\right] + V_p\left[\binom{n+1}{k}\right] \geq a.$

This will imply that $p^a$ divides $\binom{n}{k} \times \binom{n+1}{k}.$

Since this demonstration will be applicable to any prime factor of $(k+1)$,
it will imply that $(k+1)$ divides $\binom{n}{k} \times \binom{n+1}{k}.$

Note
By assumption, $~a \geq 1 \implies p~$ relatively prime to $~k \implies V_p(k) = 0$.

Let $b = V_p(n+2).$

---

$\underline{\text{Case 1 :}~ b \geq a}$

Since $p^a$ divides both $(n+2)$ and $(k+1)$, it also divides $(n-k+1).$

Therefore, $V_p(n-k+1) \geq a.$

Further, since $$\binom{n}{k-1} ~=~ \frac{n!}{(k-1)![(n-k+1)!]} ~~\text{is an integer}$$

$$V_p(n!) - V_p[(k-1)!] - V_p[(n-k+1)!] \geq 0.$$

Since $$V_p(k) = 0, ~~V_p(k!) = V_p[(k-1)!].$$

Further, $$V_p[(n-k+1)!] ~=~ V_p[(n-k)!] + V_p(n-k+1) ~\geq~ V_p[(n-k)!] + a.$$

Therefore,

$$V_p(n!) - Vp(k!) - V_p[(n-k)!] \geq a ~\implies~ $$

$$p^a \left| \frac{n!}{(k!)[(n-k)!]} = \binom{n}{k}\right.. \tag1$$

---

$\underline{\text{Case 2 :}~ b < a}$

By assumption in Case 2, $V_p(n+2) = b.$

Further, since $p^b$ divides both $(n+2)$ and $(k+1)$, it also divides $(n-k+1).$

Therefore, $V_p(n-k+1) \geq b.$

All of the corresponding analysis from Case 1 will apply here, and will lead to the conclusion that parallels equation (1) above:

$$p^b \left|\binom{n}{k}\right..$$

Therefore, it only remains to demonstrate that

$$p^{(a-b)} \left|\binom{n+1}{k}\right..$$

Since

$$\binom{n+2}{k+1} = \frac{(n+2)!}{[(k+1)!][(n-k+1)!]} ~~\text{is an integer}$$

$$V_p[(n+2)! - V_p[(k+1)! - V_p[(n-k+1)!] \geq 0.$$

Also, $\displaystyle V_p[(n+2)!] = V_p(n+2) + V_p[(n+1)!] = b + V_p[(n+1)!].$

Also, $\displaystyle V_p[(k+1)!] = V_p(k+1) + V_p(k!) = a + V_p(k!).$

Therefore,

$$V_p[(n+1)!] ~+~ b ~-~ [V_p(k!) + a] ~-~ V_p[(n-k+1)!] ~\geq~ 0~ \implies $$

$$V_p[(n+1)!] - V_p(k!) - V_p[(n-k+1)!] \geq (a-b) \implies$$

$$p^{(a-b)} \left| \frac{(n+1)!}{(k!)[(n-k+1)!]} = \binom{n+1}{k}\right..$$