Prove by induction that nCk is always a natural number

[nietzsche]

Homework Statement

Prove by induction that $$\binom{n}{k}$$ is always a natural number.

Homework Equations

The problem requires that we use the fact that
$$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}\tag{1}$$

The Attempt at a Solution

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

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

and from (1) we obtain that, with n=1, k=1,
$$\binom{n+1}{k}=\binom{2}{1}=1+1=2$$

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

Thanks in advance for your help.

 

[tiny-tim]

Hi nietzsche!

I think you're making a mountain out of a molehill …

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) )

 

[nietzsche]

Hi nietzsche!

I think you're making a mountain out of a molehill …

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) )

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.

 

[nietzsche]

https://www.physicsforums.com/showthread.php?t=61891

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

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

Not sure if what I'm saying is valid. What do yall think?

 

[tiny-tim]

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 … "

 

[nietzsche]

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 … "

Thank you very much.