Question

Combinatorics

Proof that Cm,h is a multiple of 'm', if 'm' is prime and greater than 'h'.

Answer 1

\[
\binom{m}{h} = \frac{m!}{h!(m-h)!}
\]

Answer 2

Sorry wio but where is the proof?

Answer 3

I'm not going to prove anything for you. I'm giving you some help.

Answer 4

Thanks wio but I knew that!! ;)

Answer 5

Something about the fact that \(m\) is prime has to be used in the proof.

Answer 6

For example, we know that if \(m\) is prime \(m-1\) is composite (or 1).

Answer 7

\[
m\frac{(m-1)(m-2)\ldots(m-h+1)}{h!}
\]

Answer 8

Actually I take that back, aside form 2-1=1 and 3-1=2, the other primes subtracting one will have compositite

Answer 9

We know that: \[I) m \in P, if and only if, \not \exists a,b \in \mathbb{Z} | ab=m\] & \[ 1<a,b<m \rightarrow m=1m \] to all \[m \in \mathbb{N} - \{0\}\]
\[II) m \notin P, if and only if \exists a,b \in \mathbb{Z} | ab=m \] and \[ 1<a,b<m \rightarrow m=ab \]to all \[m \in \mathbb{N} - \{0\}\]

Answer 10

Okay so consider that \[
\binom mh,\binom {m-1}h\in \mathbb N
\]

Answer 11

Now \[
\binom mn = \frac{m!}{h!(m-h)!} = \frac{m}{m-h} \cdot \frac{(m-1)!}{h!(m-h-1)!}=\frac{m}{m-h}\binom {m-1}h
\]

Answer 12

We know \(m-h\) has to divide either \(m\) or \(\binom {m-1}h\).
If it didn't, them \(\binom mh\) wouldn't be a natural number.

Answer 13

It can only divide \(m\) if \(m-h=1\) or \(m-h=m\).
If \(m-h=1\) then it divides \(\binom{m-1}h\) as well. since \(1\) divides all numbers.
If \(m-h=m\) then \(h=0\). Since \(\binom m0=1\) I assume we ignore this case.

Answer 14

If \(m-h\) doesn't divide \(m\), then it must divide \(\binom{m-1}h\).
If it doesn't divide \(m\) or \(\binom{m-1}h\) that would mean \(\binom mh\) isn't a natural number which is a contradiction.

Answer 15

Thus assuming \(m>h>0\) and \(m\) is prime,
In all cases, \(m-h\) divides \(\binom{m-1}{h}\). Let us call the result of the division \(n\in \mathbb N\).

Answer 16

This means \[
\binom mh = mn
\]

Answer 17

So since \(m\) divides \(\binom mh\), \(m\) is a multiple of it.

Answer 18

There is your proof.

Answer 19

Thanks for the idea, wio. I'm going to try to use it.
I'll tell you.

Answer 20

\[P =\left\{ m \in \mathbb{Z}^+| !\exists a,b \in N| ab=m \rightarrow m=m1\right\}\]
\[\forall a,b \in \mathbb{Z}^+\]
Hypothesis:
\[\left(\begin{matrix}a \\ b\end{matrix}\right) = ax \forall a \in P | ax \in \mathbb{Z}^+ , ax \in N\]
\[a >b \rightarrow a - b > 0 \forall ab \in N\]
1) a=b+1; \[\left(\begin{matrix}a \\ b\end{matrix}\right) = a; x=1\]
2) a=b+2; \[\left(\begin{matrix}a \\ b\end{matrix}\right) = (a/2!)(a-1); x=(a-1)/2!\]
3) a=b+3; \[\left(\begin{matrix}a \\ b\end{matrix}\right) = (a/3!)(a-1)(a-2); x=((a-1)(a-2))/3!\]
...
n) a= b+n; \[\left(\begin{matrix}a \\ b\end{matrix}\right) = (a/n!)(a-1)(a-2)...(a-n+1);x=((a-1)(a-2)...(a-n+1))/n!\]
\[\left(\begin{matrix}a \\ b\end{matrix}\right) = (\prod_{k=0}^{n-1}a-k)/(\prod_{k=1}^{n}k)\]
\[x=(\prod_{k=1}^{n-1}a-k)/(\prod_{k=1}^{n}k)\]
Hypothesis said: \[ax=\left(\begin{matrix}a \\ b\end{matrix}\right)\]

\[(a \prod_{k=1}^{n-1}a-k)/(\prod_{k=1}^{n}k)=(\prod_{k=0}^{n-1}a-k)/(\prod_{k=1}^{n}k)=\left(\begin{matrix}a \\ b\end{matrix}\right)\]