Proving the binomial coeficient is always a natural number?

**mfetch22** · July 20th 2010, 06:59 AM

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

**chiph588@** · July 20th 2010, 07:38 AM

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)

**undefined** · July 20th 2010, 07:46 AM

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.

**Unbeatable0** · July 20th 2010, 03:43 PM

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}$

**simplependulum** · July 20th 2010, 10:50 PM

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}$ .

**Archie Meade** · July 21st 2010, 03:02 PM

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.

Thread: Proving the binomial coeficient is always a natural number?

LinkBack

Thread Tools

Display

Proving the binomial coeficient is always a natural number?

Similar Math Help Forum Discussions

For each natural number n, let An=(x in the real #s such that...

Prove that every natural number is either even or odd?

Proving Abel's theorem of 'natural irrationalities' using Galois Theory

Prove that the binomial coefficient is always a natural number?

Prove natural number

Search Tags