Waste less time on Facebook — follow Brilliant.
×

How to prove this?

Please also provide a counter-example if this conjecture is invalid.

Let \(a_1,a_2,\cdots,a_n\) be positive integers such that \(\displaystyle a=\sum_{i=1}^na_i\).

Prove that: \[\frac{a!}{\prod_{i=1}^na_i!}\in\mathbb N\]

P.S. I currently have no solution. Help is much appreciated.

Note by Kenny Lau
1 year, 6 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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 · 1 year, 6 months ago

Log in to reply

@Paulo Guilherme Santos Where is a complete proof from zero very justified. Hope you enjoy! Paulo Guilherme Santos · 1 year, 6 months ago

Log in to reply

Comment deleted Jul 24, 2015

Log in to reply

@Paulo Guilherme Santos There's a tiny problem in your first lemma. You showed that all elements of \(A\) divide at least one element of \(B\), but not that the product of all elements of \(A\) divides the product of all elements of \(B\). Kenny Lau · 1 year, 6 months ago

Log in to reply

Comment deleted Jul 24, 2015

Log in to reply

@Paulo Guilherme Santos That cannot be proved so simply. For example, \(A=\{4,5,6\}\) and \(B=\{1,5,24\}\) satisfy the condition but not the result. Being consecutive numbers adds no validity. Kenny Lau · 1 year, 6 months ago

Log in to reply

Comment deleted Jul 24, 2015

Log in to reply

@Paulo Guilherme Santos You have not used "they are consecutive numbers" in this step:

  • proven: "all elements in A divide at least one element in B"
  • result: "product of all elements in A divide product of all elements in B"
Kenny Lau · 1 year, 6 months ago

Log in to reply

Comment deleted Jul 24, 2015

Log in to reply

@Paulo Guilherme Santos Edited. Kenny Lau · 1 year, 6 months ago

Log in to reply

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 · 1 year, 6 months ago

Log in to reply

This is the expression for the number of Permutations with Repetition, and hence must always be a natural number. Brian Charlesworth · 1 year, 6 months ago

Log in to reply

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

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...