How to prove this?

Let's prove, in the first place, that

\(\forall a,n \in \mathbb{N}, \displaystyle\frac{\displaystyle\prod_{i=1}^n \left( a+i \right)}{n!} \in \mathbb{N} \). \( (1) \)

Let \( a \in \mathbb{N} \).

For that achievement, I will prove that

\( \forall i \in \{1,...,n \}, \exists j \in \{a+1,..., a+n \}: i|j \).

Let's suppose, in first place, by reductio ad absurdum, that \( \nexists j \in \{a+1,..., a+n \}: n|j \). Let \(m_1= \max \{j \in \mathbb{N}: n|j \land j\leq a \} \). Let's consider \( m_1+n \). We have that, by hypothesis, \( \nexists j \in \{a+1,..., a+n \}: n|j \), so \( m_1+n>a+n \). By definition of \( m_1 \), we have that \(m_1 \leq a \iff -m_1 \geq -a \). We can conclude that

\(m_1+n>a+n \iff n>a+n-m_1 \implies n>a+n-a \implies n>n \)

which is an absurdum, so \( \exists j \in \{a+1,..., a+n \}: n|j \).

Now, let \( i \in \{1,...,n-1 \} \). Let's suppose, in these conditions, by reductio ad absurdum, that \( \nexists j \in \{a+1,..., a+n \}: i|j \). Let \(m_2= \max \{j \in \mathbb{N}: i|j \land j<a+1 \} \). By definition of \( m_2 \), we have that \(m_2<a+1 \iff -m_2>-(a+1) \). Now, let's consider \(m_2+i \). By hypothesis we have that \( \nexists j \in \{a+1,..., a+n \}: i|j \), so \(m_2+i>a+n \). We can conclude that

\(m_2+i>a+n \iff i>a+n-m_2 \implies i>a+n-(a+1) \implies i>n-1 \implies i \notin \{1,...,n-1 \} \)

which is an absurdum, as wanted. So we have that

\( \forall i \in \{1,...,n \}, \exists j \in \{a+1,..., a+n \}: i|j \).

Let's consider, for each \(i \in \{1,...,n \} \), \(A_i= \{ n \in \{a+1,..., a+n \}: i|n \} \), and \(A= \{A_i: i \in \{1,...,n \} \} \). As \( \forall i \in \{1,...,n \}, A_i \neq \emptyset \), we conclude that \(A \neq \emptyset \). By the Axiom of Choice, we have that

\( \exists f \in \mathscr{F} \left( A, \bigcup A \right): \forall X \in A, f(X) \in X \) .

Let \(f \in \mathscr{F} \left( A, \bigcup A \right) \) be in that conditions. In these conditions, by the definition of \(f \), it is clear that

\(\displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} \in \mathbb{N} \).

Let \( b \in \mathbb{N} \) be such that \( b= \displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} \) and let \(Y= \{f(A_i): i \in \{1,...,n \} \} \). We have that

\(\displaystyle\frac{\displaystyle\prod_{i=1}^n \left( a+i \right)}{n!}=\displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} \cdot \left(\displaystyle\prod\nolimits_{a_i \in\{a+1,..., a+n \}\setminus Y} \left( a_i \right)\right)=b \cdot \left(\displaystyle\prod\nolimits_{a_i \in\{a+1,..., a+n \}\setminus Y} \left( a_i \right)\right) \in \mathbb{N} \)

As wanted.

Now, let's prove that

\( \forall {\left( a_i \right)}_{i \in \{1,...,n\} } \in {\mathbb{N}}^n, \displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \in \mathbb{N} \).

Let \(C= \Bigg\{n \in \mathbb{N}: \forall {\left( a_i \right)}_{i \in \{1,...,n \} } \in {\mathbb{N}}^n, \displaystyle\frac{ \left(\sum_{i=1}^n a_i \right)! }{\prod_{i=1}^n a_i !} \in \mathbb{N} \Bigg\} \). Let \(a_1 \in \mathbb{N} \). We have that

\(\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^1 a_i \right)! }{\displaystyle\prod_{i=1}^1 a_i !}=\displaystyle\frac{a_1!}{a_1!}=1 \in \mathbb{N} \)

So, \( 1 \in C \). Now, let's suppose, by induction hypothesis, that \( n \in \mathbb{N} \). Let \( {\left( a_i \right)}_{i \in \{1,...,n+1 \} } \in {\mathbb{N}}^{n+1} \). We have that

\(\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^{n+1} a_i \right)! }{\displaystyle\prod_{i=1}^{n+1} a_i !}=\displaystyle\frac{ \left(\left(\displaystyle\sum_{i=1}^n a_i \right)+a_{n+1}\right)! }{\left(\displaystyle\prod_{i=1}^n a_i !\right) \cdot a_{n+1}!}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !}\cdot \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!} \)

By induction hypothesis, we have that

\(\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \in \mathbb{N} \). Let \(d \in \mathbb{N} \) be such that \(d=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \). Let \(v=a_{n+1} \) and \(S= \left(\displaystyle\sum_{i=1}^n a_i \right) \). It is clear that

\( \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!}= \displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!}\)

Applying \( (1) \), we conclude that

\(\displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!} \in \mathbb{N} \). Let \(p \in \mathbb{N} \) be such that \(p=\displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!} \). In these conditions we have that

\( \displaystyle\frac{ \left(\displaystyle\sum_{i=1}^{n+1} a_i \right)! }{\displaystyle\prod_{i=1}^{n+1} a_i !}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !}\cdot \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \cdot \displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!}=d \cdot p \in \mathbb{N} \), because \(d,p \in \mathbb{N} \).

In these conditions we can conclude that \(n+1 \in C \). In sum, \(C= \mathbb{N} \); so,

\( \forall {\left( a_i \right)}_{i \in \{1,...,n\} } \in {\mathbb{N}}^n, \displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \in \mathbb{N} \).

QED – Paulo Guilherme Santos · 2 years ago

Apart from what Brian suggested (but similar), you can also note that your expression is the multinomial coefficient \(\dbinom{a}{a_1,a_2,\ldots, a_n}\) which must be an integer if you use the combinatorial interpretation.

For some purely arithmetical / number-theoretical proofs, see this and choose the answer you find best. – Prasun Biswas · 2 years ago

This is the expression for the number of Permutations with Repetition, and hence must always be a natural number. – Brian Charlesworth · 2 years ago

Do you find my proof clear? – Paulo Guilherme Santos · 1 year, 12 months ago