My Math Forum (http://mymathforum.com/math-forums.php)

 Jomo March 28th, 2018 03:26 PM

Combinatoric question

I was wondering how one could prove that nCr is an integer. Yes, I do know that you can say that it is by definition but I was looking for a proof not involving a counting argument.

 cjem March 28th, 2018 04:05 PM

It really depends on what definition you're using for nCr.

If the one you're using is such that it's an integer by definition, then it's an integer by definition! No counting argument necessary. Otherwise, it would not be okay to say it's an integer by definition.

 Jomo March 28th, 2018 08:21 PM

Quote:
 Originally Posted by cjem (Post 590918) It really depends on what definition you're using for nCr. If the one you're using is such that it's an integer by definition, then it's an integer by definition! No counting argument necessary. Otherwise, it would not be okay to say it's an integer by definition.
All I want to use is that nCr = n!/(r!(n-r)!). Why is that an integer?

 cjem March 29th, 2018 03:10 AM

Okay, sure. I'm in a bit of a rush right now, so I'll write up a very brief argument. I'll be happy to clarify things later if needed.

What we want to show is that $r!$ divides $\dfrac{n!}{(n-r)!}$.

Let $p$ be a prime, and denote by $\nu_p$ the $p$-adic valuation. It's not hard to show that $\nu_p(x!) = \sum_{t \geq 1} \left\lfloor \dfrac{x}{p^t} \right\rfloor$ for any integer $x$. Therefore

\begin{align*} \nu_p \left(\dfrac{n!}{(n-r)!}\right) &= \nu_p (n!) - \nu_p ((n-r)!) \\ &= \sum_{t \geq 1} \left\lfloor \dfrac{n}{p^t} \right\rfloor - \sum_{t \geq 1} \left\lfloor \dfrac{n-r}{p^t} \right\rfloor \\ &\geq \sum_{t \geq 1} \left\lfloor \dfrac{r}{p^t} \right\rfloor \\ &= \nu_p(r!) \end{align*}

 SDK March 29th, 2018 05:22 AM

A slightly more elementary observation (which I think is the reason for the inequality on the 2nd to last line in cjem's solution thought I'm not sure) is the following fact.

Fix $m \in \mathbb{N}$ and let $P$ be the product of $m$-many consecutive positive integers Then $m! \leq P$. This is fairly easy to prove. Here is a sketch which may help.

$P$ has the form
$P = \prod_{j = 1}^m (k + j)$
for some $k \in \mathbb{N}$. Obviously we have equality if $k = 0$. Now, fix any prime $q \in \mathbb{N}$ and argue the following:

1. $P$ has at least as many multiples of $q$ as $m!$ does. To see this, count the multiples of $q$ when you reduce any $m$ consecutive integers modulo $q$.

2. The result in 1 also holds if we replace $q$ with powers of $q$.

3. For each prime, $q$, dividing $m!$, each occurrence is either a multiple of $q$ or a multiple of $q^s$ with $s >1$. The results in (1),(2) says $P$ has at least as many occurrences of each of these as $m!$ so $P$ has at least as many occurrences of $q$ as $m!$ does.

This result holds for any $m \in \mathbb{N}$. Do you see why this now immediately implies that $\binom{n}{k}$ is an integer?

 cjem March 29th, 2018 06:15 AM

Quote:
 Originally Posted by SDK (Post 590970) A slightly more elementary observation (which I think is the reason for the inequality on the 2nd to last line in cjem's solution thought I'm not sure) is the following fact. Fix $m \in \mathbb{N}$ and let $P$ be the product of $m$-many consecutive positive integers Then $m! \leq P$. This is fairly easy to prove. Here is a sketch which may help.
The inequality simply comes from $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \leq \left \lfloor x + y \right \rfloor$:

For any $t$, we have $\left\lfloor \dfrac{n-r}{p^t} \right\rfloor + \left\lfloor \dfrac{r}{p^t} \right\rfloor \leq \left\lfloor \dfrac{(n-r)+r}{p^t} \right\rfloor = \left\lfloor \dfrac{n}{p^t} \right\rfloor$. Hence $\left\lfloor \dfrac{n}{p^t} \right\rfloor - \left\lfloor \dfrac{n-r}{p^t} \right\rfloor \geq \left\lfloor \dfrac{r}{p^t} \right\rfloor$. Now just sum over $t$ to get the inequality in my post.

 Micrm@ss March 29th, 2018 07:03 AM

Or you could use an induction and
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

 Jomo March 29th, 2018 03:21 PM

Quote:
 Originally Posted by SDK (Post 590970) A slightly more elementary observation (which I think is the reason for the inequality on the 2nd to last line in cjem's solution thought I'm not sure) is the following fact. Fix $m \in \mathbb{N}$ and let $P$ be the product of $m$-many consecutive positive integers Then $m! \leq P$. This is fairly easy to prove. Here is a sketch which may help. $P$ has the form $P = \prod_{j = 1}^m (k + j)$ for some $k \in \mathbb{N}$. Obviously we have equality if $k = 0$. Now, fix any prime $q \in \mathbb{N}$ and argue the following: 1. $P$ has at least as many multiples of $q$ as $m!$ does. To see this, count the multiples of $q$ when you reduce any $m$ consecutive integers modulo $q$. 2. The result in 1 also holds if we replace $q$ with powers of $q$. 3. For each prime, $q$, dividing $m!$, each occurrence is either a multiple of $q$ or a multiple of $q^s$ with $s >1$. The results in (1),(2) says $P$ has at least as many occurrences of each of these as $m!$ so $P$ has at least as many occurrences of $q$ as $m!$ does. This result holds for any $m \in \mathbb{N}$. Do you see why this now immediately implies that $\binom{n}{k}$ is an integer?
Yes, I followed this. Thank you.

 Jomo March 29th, 2018 03:25 PM

Quote:
 Originally Posted by cjem (Post 590964) Okay, sure. I'm in a bit of a rush right now, so I'll write up a very brief argument. I'll be happy to clarify things later if needed. What we want to show is that $r!$ divides $\dfrac{n!}{(n-r)!}$. Let $p$ be a prime, and denote by $\nu_p$ the $p$-adic valuation. It's not hard to show that $\nu_p(x!) = \sum_{t \geq 1} \left\lfloor \dfrac{x}{p^t} \right\rfloor$ for any integer $x$. Therefore \begin{align*} \nu_p \left(\dfrac{n!}{(n-r)!}\right) &= \nu_p (n!) - \nu_p ((n-r)!) \\ &= \sum_{t \geq 1} \left\lfloor \dfrac{n}{p^t} \right\rfloor - \sum_{t \geq 1} \left\lfloor \dfrac{n-r}{p^t} \right\rfloor \\ &\geq \sum_{t \geq 1} \left\lfloor \dfrac{r}{p^t} \right\rfloor \\ &= \nu_p(r!) \end{align*}