# Proving the binomial coeficient is always a natural number?

• Jul 20th 2010, 06:59 AM
mfetch22
Proving the binomial coeficient is always a natural number?
How would one go about proving that:

$\displaystyle { n \choose k }$

is always a natural number? That is, assuming $\displaystyle 0 \leq k \leq n$ and that $\displaystyle n = 1, 2, 3, 4...$ and that $\displaystyle k = 1, 2, 3, 4...$; what I mean by that is that $\displaystyle n$ and $\displaystyle 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
• Jul 20th 2010, 07:38 AM
chiph588@
Quote:

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

$\displaystyle { n \choose k }$

is always a natural number? That is, assuming $\displaystyle 0 \leq k \leq n$ and that $\displaystyle n = 1, 2, 3, 4...$ and that $\displaystyle k = 1, 2, 3, 4...$; what I mean by that is that $\displaystyle n$ and $\displaystyle 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 \displaystyle{\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ for $\displaystyle \displaystyle{k=1\ldots n-1}$ and $\displaystyle \displaystyle{\binom{n}{0}=\binom{n}{n}=1}$.

(This will be a proof by induction)
• Jul 20th 2010, 07:46 AM
undefined
Quote:

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

$\displaystyle { n \choose k }$

is always a natural number? That is, assuming $\displaystyle 0 \leq k \leq n$ and that $\displaystyle n = 1, 2, 3, 4...$ and that $\displaystyle k = 1, 2, 3, 4...$; what I mean by that is that $\displaystyle n$ and $\displaystyle 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 \displaystyle { n \choose k }$ can be shown to equal either of the two equivalent quantities

1) the coefficient of the $\displaystyle \displaystyle x^k$ term in the polynomial expansion of the binomial power $\displaystyle \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.
• Jul 20th 2010, 03:43 PM
Unbeatable0
Another way is to use Legendre's formula, which states that ($\displaystyle \mathbb{P}$ is the set of prime numbers)

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

Thus for any prime $\displaystyle p$ we have:

$\displaystyle \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 $\displaystyle \lfloor{x+y}\rfloor \ge \lfloor{x}\rfloor + \lfloor{y}\rfloor$

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

$\displaystyle \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 $\displaystyle \binom{n}{k} \in \mathbb{N}$
• Jul 20th 2010, 10:50 PM
simplependulum
Quote:

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

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

Thus for any prime $\displaystyle p$ we have:

$\displaystyle \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 $\displaystyle \lfloor{x+y}\rfloor \ge \lfloor{x}\rfloor + \lfloor{y}\rfloor$

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

$\displaystyle \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 $\displaystyle \binom{n}{k} \in \mathbb{N}$

Perfect , in fact $\displaystyle \lfloor{ x+y \rfloor} = \lfloor{ x \rfloor} + \lfloor{ y \rfloor} + \lfloor{ \{ x \} + \{ y \} \rfloor} \geq \lfloor{ x \rfloor} + \lfloor{ y \rfloor}$ .
• Jul 21st 2010, 03:02 PM
Quote:

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

$\displaystyle { n \choose k }$

is always a natural number? That is, assuming $\displaystyle 0 \leq k \leq n$ and that $\displaystyle n = 1, 2, 3, 4...$ and that $\displaystyle k = 1, 2, 3, 4...$; what I mean by that is that $\displaystyle n$ and $\displaystyle 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...

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

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

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

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

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

If the "a" values were labelled $\displaystyle 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

$\displaystyle \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 $\displaystyle \frac{n!}{k!}$ as k! has been "cut off" the tail.

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