Results 1 to 6 of 6

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

  1. #1
    Member mfetch22's Avatar
    Joined
    Feb 2010
    From
    Columbus, Ohio, USA
    Posts
    168

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by mfetch22 View Post
    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)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mfetch22 View Post
    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.
    Last edited by undefined; July 20th 2010 at 09:11 AM. Reason: very small typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2009
    Posts
    106
    Another way is to use Legendre's formula, which states that ( \mathbb{P} is the set of prime numbers)

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

    Thus for any prime p we have:

    <br />
\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}}<br />

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

    <br />
\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<br />

    and therefore \binom{n}{k} \in \mathbb{N}
    Last edited by Unbeatable0; July 25th 2010 at 07:37 AM. Reason: Confused Legendre with Leibnitz
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Quote Originally Posted by Unbeatable0 View Post
    Another way is to use Leibnitz' formula, which states that ( \mathbb{P} is the set of prime numbers)

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

    Thus for any prime p we have:

    <br />
\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}}<br />

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

    <br />
\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<br />

    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}  .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by mfetch22 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 14th 2011, 03:46 AM
  2. Prove that every natural number is either even or odd?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 20th 2010, 09:35 AM
  3. Replies: 0
    Last Post: July 19th 2010, 06:19 AM
  4. Replies: 2
    Last Post: July 14th 2010, 03:16 PM
  5. Prove natural number
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 25th 2009, 10:55 AM

Search Tags


/mathhelpforum @mathhelpforum