How to prove this?

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

Let a1,a2,,ana_1,a_2,\cdots,a_n be positive integers such that a=i=1nai\displaystyle a=\sum_{i=1}^na_i.

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

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

#Combinatorics #NumberTheory

Note by Kenny Lau
5 years, 10 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

This is the expression for the number of Permutations with Repetition, and hence must always be a natural number.

Brian Charlesworth - 5 years, 10 months ago

Apart from what Brian suggested (but similar), you can also note that your expression is the multinomial coefficient (aa1,a2,,an)\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 - 5 years, 10 months ago

Let's prove, in the first place, that

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

Let aN a \in \mathbb{N} .

For that achievement, I will prove that

i{1,...,n},j{a+1,...,a+n}:ij \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 j{a+1,...,a+n}:nj \nexists j \in \{a+1,..., a+n \}: n|j . Let m1=max{jN:njja}m_1= \max \{j \in \mathbb{N}: n|j \land j\leq a \} . Let's consider m1+n m_1+n . We have that, by hypothesis, j{a+1,...,a+n}:nj \nexists j \in \{a+1,..., a+n \}: n|j , so m1+n>a+n m_1+n>a+n . By definition of m1 m_1 , we have that m1a    m1am_1 \leq a \iff -m_1 \geq -a . We can conclude that

m1+n>a+n    n>a+nm1    n>a+na    n>nm_1+n>a+n \iff n>a+n-m_1 \implies n>a+n-a \implies n>n

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

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

m2+i>a+n    i>a+nm2    i>a+n(a+1)    i>n1    i{1,...,n1}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

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

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

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

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

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

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

i=1n(a+i)n!=i=1nf(Ai)n!(ai{a+1,...,a+n}Y(ai))=b(ai{a+1,...,a+n}Y(ai))N\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

(ai)i{1,...,n}Nn,(i=1nai)!i=1nai!N \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={nN:(ai)i{1,...,n}Nn,(i=1nai)!i=1nai!N}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 a1Na_1 \in \mathbb{N} . We have that

(i=11ai)!i=11ai!=a1!a1!=1N\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, 1C 1 \in C . Now, let's suppose, by induction hypothesis, that nN n \in \mathbb{N} . Let (ai)i{1,...,n+1}Nn+1 {\left( a_i \right)}_{i \in \{1,...,n+1 \} } \in {\mathbb{N}}^{n+1} . We have that

(i=1n+1ai)!i=1n+1ai!=((i=1nai)+an+1)!(i=1nai!)an+1!=(i=1nai)!i=1nai!k=1an+1((i=1nai)+k)an+1!\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

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

k=1an+1((i=1nai)+k)an+1!=k=1v(S+k)v! \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) (1) , we conclude that

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

(i=1n+1ai)!i=1n+1ai!=(i=1nai)!i=1nai!k=1an+1((i=1nai)+k)an+1!=(i=1nai)!i=1nai!k=1v(S+k)v!=dpN \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,pNd,p \in \mathbb{N} .

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

(ai)i{1,...,n}Nn,(i=1nai)!i=1nai!N \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 - 5 years, 10 months ago

Log in to reply

Where is a complete proof from zero very justified. Hope you enjoy!

Paulo Guilherme Santos - 5 years, 10 months ago

Do you find my proof clear?

Paulo Guilherme Santos - 5 years, 10 months ago
×

Problem Loading...

Note Loading...

Set Loading...