1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove by induction that nCk is always a natural number

  1. Sep 21, 2009 #1
    1. The problem statement, all variables and given/known data

    Prove by induction that [tex]\binom{n}{k}[/tex] is always a natural number.


    2. Relevant equations

    The problem requires that we use the fact that
    [tex]\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}\tag{1}[/tex]


    3. The attempt at a solution

    Well, the first part of this question requires a proof of (1), which was easy enough just using
    [tex]\binom{n}{k}=\frac{n!}{k!(n-k)!}[/tex]

    What I'm not sure of is how to perform the induction. I took the base case of n=1.
    [tex]\binom{1}{0}=1[/tex]
    [tex]\binom{1}{1}=1[/tex]

    and from (1) we obtain that, with n=1, k=1,
    [tex]\binom{n+1}{k}=\binom{2}{1}=1+1=2[/tex]

    Can I now say that [tex]\binom{n+1}{k}[/tex] is always the sum of two natural numbers, and is therefore natural?

    Thanks in advance for your help.
     
  2. jcsd
  3. Sep 22, 2009 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi nietzsche! :smile:

    I think you're making a mountain out of a molehill :redface:

    to prove (7 5) is an integer, all you need is that (6 5) and (6 4) are integers …

    so just be systematic in what order you do the proof

    (and remember it doesn't work for k = 0, so you have to prove it for all (n 0) separately, not just for (1 0) :wink:)
     
  4. Sep 22, 2009 #3
    I've no clue as to how to prove that (6 5) and (6 4) are integers. Do I still have to consider a base case of n=1? This question is driving me mad.
     
  5. Sep 22, 2009 #4
    https://www.physicsforums.com/showthread.php?t=61891

    I found this, which is the same question. According to this,

    [tex]
    \text{Let }n=0.
    \text{ If }k=0,
    \binom{0}{0} = 1
    \text{ (by definition)}
    \text{ and if }k \not= 0,
    \binom{0}{k} = 0
    \text{ (by definition).}
    [/tex]
    [tex]
    \text{Since}
    \binom{n+1}{k} = \binom{n}{k-1}+\binom{n}{k},
    \text{ it follows from induction that for all }
    n, \binom{n}{k}
    \text{is an integer.}
    [/tex]

    Not sure if what I'm saying is valid. What do yall think?
     
  6. Sep 22, 2009 #5

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yes, if you're happy with (n k) = 0 for n < k, then that proof is correct.

    But you need to specify the ordering …

    Start: "It works for n = 0 and for any k, and then by induction on n … " :smile:
     
  7. Sep 22, 2009 #6
    Thank you very much.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove by induction that nCk is always a natural number
  1. Nature of this number (Replies: 13)

  2. Natural number (Replies: 35)

  3. Prove by Induction (Replies: 2)

  4. Prove by induction (Replies: 5)

  5. Prove by Induction (Replies: 17)

Loading...