# Math Help - Proving the binomial coeficient is always a natural number?

1. ## Proving the binomial coeficient is always a natural number?

How would one go about proving that:

${ n \choose k }$

is always a natural number? That is, assuming $0 \leq k \leq n$ and that $n = 1, 2, 3, 4...$ and that $k = 1, 2, 3, 4...$; what I mean by that is that $n$ and $k$ are both positive integers. Its a question in my textbook that I bought early to get ahead on fall classes, so I don't have any teachers to ask about this question; not till fall atleast. I'm not asking for a straight out proof, but preferably some direction as to where I would go, which direction I should go to prove this? A litttle guidence is all I need, please don't simply give me the full answer, if you don't mind. Thanks in advance

2. Originally Posted by mfetch22
How would one go about proving that:

${ n \choose k }$

is always a natural number? That is, assuming $0 \leq k \leq n$ and that $n = 1, 2, 3, 4...$ and that $k = 1, 2, 3, 4...$; what I mean by that is that $n$ and $k$ are both positive integers. Its a question in my textbook that I bought early to get ahead on fall classes, so I don't have any teachers to ask about this question; not till fall atleast. I'm not asking for a straight out proof, but preferably some direction as to where I would go, which direction I should go to prove this? A litttle guidence is all I need, please don't simply give me the full answer, if you don't mind. Thanks in advance
Use the fact that $\displaystyle{\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ for $\displaystyle{k=1\ldots n-1}$ and $\displaystyle{\binom{n}{0}=\binom{n}{n}=1}$.

(This will be a proof by induction)

3. Originally Posted by mfetch22
How would one go about proving that:

${ n \choose k }$

is always a natural number? That is, assuming $0 \leq k \leq n$ and that $n = 1, 2, 3, 4...$ and that $k = 1, 2, 3, 4...$; what I mean by that is that $n$ and $k$ are both positive integers. Its a question in my textbook that I bought early to get ahead on fall classes, so I don't have any teachers to ask about this question; not till fall atleast. I'm not asking for a straight out proof, but preferably some direction as to where I would go, which direction I should go to prove this? A litttle guidence is all I need, please don't simply give me the full answer, if you don't mind. Thanks in advance
There's also the combinatorial proof. (The binomial coefficient is given as an "archetypal example" not far from the top of the page.) The formula(s) given for $\displaystyle { n \choose k }$ can be shown to equal either of the two equivalent quantities

1) the coefficient of the $\displaystyle x^k$ term in the polynomial expansion of the binomial power $\displaystyle (1 + x)^n$
2) the number of ways to choose k elements from a set of n elements. (The number of distinct k-subsets of {1, 2, ... , n}.)

Obviously both of these quantities are integers.

4. Another way is to use Legendre's formula, which states that ( $\mathbb{P}$ is the set of prime numbers)

$
n! = \prod_{p\in \mathbb{P}} p^{\sum_{i=1}^\infty \Big\lfloor\frac{n}{p^i}\Big\rfloor}
$

Thus for any prime $p$ we have:

$
\binom{n}{k} = \frac{n!}{k!(n-k)!} = \prod_{p\in \mathbb{P}} p^{\sum_{i=1}^\infty \Big\lfloor\frac{n}{p^i}\Big\rfloor-\Big\lfloor\frac{k}{p^i}\Big\rfloor-\Big\lfloor\frac{n-k}{p^i}\Big\rfloor}}
$

So all what's left is to show that $\lfloor{x+y}\rfloor \ge \lfloor{x}\rfloor + \lfloor{y}\rfloor$

so it follows that for all $i\in\mathbb{N}$:

$
\Big\lfloor\frac{n}{p^i}\Big\rfloor-\Big\lfloor\frac{k}{p^i}\Big\rfloor-\Big\lfloor\frac{n-k}{p^i}\Big\rfloor} \ge 0
$

and therefore $\binom{n}{k} \in \mathbb{N}$

5. Originally Posted by Unbeatable0
Another way is to use Leibnitz' formula, which states that ( $\mathbb{P}$ is the set of prime numbers)

$
n! = \prod_{p\in \mathbb{P}} p^{\sum_{i=1}^\infty \Big\lfloor\frac{n}{p^i}\Big\rfloor}
$

Thus for any prime $p$ we have:

$
\binom{n}{k} = \frac{n!}{k!(n-k)!} = \prod_{p\in \mathbb{P}} p^{\sum_{i=1}^\infty \Big\lfloor\frac{n}{p^i}\Big\rfloor-\Big\lfloor\frac{k}{p^i}\Big\rfloor-\Big\lfloor\frac{n-k}{p^i}\Big\rfloor}}
$

So all what's left is to show that $\lfloor{x+y}\rfloor \ge \lfloor{x}\rfloor + \lfloor{y}\rfloor$

so it follows that for all $i\in\mathbb{N}$:

$
\Big\lfloor\frac{n}{p^i}\Big\rfloor-\Big\lfloor\frac{k}{p^i}\Big\rfloor-\Big\lfloor\frac{n-k}{p^i}\Big\rfloor} \ge 0
$

and therefore $\binom{n}{k} \in \mathbb{N}$
Perfect , in fact $\lfloor{ x+y \rfloor} = \lfloor{ x \rfloor} + \lfloor{ y \rfloor} + \lfloor{ \{ x \} + \{ y \} \rfloor} \geq \lfloor{ x \rfloor} + \lfloor{ y \rfloor}$ .

6. Originally Posted by mfetch22
How would one go about proving that:

${ n \choose k }$

is always a natural number? That is, assuming $0 \leq k \leq n$ and that $n = 1, 2, 3, 4...$ and that $k = 1, 2, 3, 4...$; what I mean by that is that $n$ and $k$ are both positive integers. Its a question in my textbook that I bought early to get ahead on fall classes, so I don't have any teachers to ask about this question; not till fall atleast. I'm not asking for a straight out proof, but preferably some direction as to where I would go, which direction I should go to prove this? A litttle guidence is all I need, please don't simply give me the full answer, if you don't mind. Thanks in advance
If you are asking from the perspective of the Binomial Expansion,
then you can observe a pattern if you refrain from expressing the terms with indices...

$(a+b)^2=(a+b)(a+b)=aa+ab+ba+bb$

"a" times "b" is expressed in both possible ways.

$(a+b)^3=(a+b)(a+b)^2=(a+b)(aa+ab+ba+bb)$

$=aaa+aab+aba+abb+baa+bab+bba+bbb$

$=aaa+aab+aba+baa+abb+bab+bba+bbb$

If the "a" values were labelled $a_1,\ a_2,\ a_3$ we could arrange them,

hence we have all possible selections of 2 "a"'s with a "b", 2 "b"'s with an "a",
the only possible selection of 3 "a"s, the only selection of 3 "b"'s.

For higher powers, the same pattern exists.
Since this pattern is the same as "choose k from n available",
the binomial coefficient may be calculated using

$\binom{n}{k}$

There are k! arrangements of a selection.
As shown above, the number of selections is a natural number,
which can be calculated by "unarranging" the arrangements.

The number of arrangements of k from n is n(n-1)(n-2)...(n-[k-1])

which is $\frac{n!}{k!}$ as k! has been "cut off" the tail.

The number of arrangements is k! times the number of selections.