Proof by induction: nCr always an integer

[sgnagni]

Hello all,

I've been asked for a graduate level course to do a proof using induction that shows that nCr always turns out to be an integer. I thought that I might use Pascal's triangle somehow and the fact that nCr is equal to n! / r!(n-r)! (I saw a brief explanation of this while doing a web search) but am not sure how to lay out the proof. This seems really really complicated... am I wrong? Any help will be much appreciated.


SG

 

[Hurkyl]

If you can prove nCr is an element of Pascal's triangle, then the rest of the proof is trivial...

 

[sgnagni]

I'm not sure I know how to prove that...

 

[Hurkyl]

So what definition of nCr are you using?

 

[sgnagni]

Proof: nCr

I am using the definition that nCr = n! / r! (n-r)!

Steve

P.S. Thank you for your help...

 

[Hurkyl]

So, you just need to prove that formula satisfies the initial conditions and recurrence relation of Pascal's triangle.

 

[sgnagni]

So, the initial conditions would be n=0, r=0?

And then what would I take as my induction hypothesis?

Steve

 

[Hurkyl]

Can you write, algebraically, how to compute Pascal's triangle?

 

[sgnagni]

Would I do it as some sort of a matrix?

Steve

 

[matt grime]

The binomial coefficients satisfy something called a recurrence relation. Surely you've seen this? How do you find nCr, as en entry in pascal's triangle, from other entries, specifically ones higher up in the triangle, even more specifically the ones immediately above it. (I'm assuming that 1C1 is at the top and the triangle cascades down.)

If you don't mind me asking, where is this a graduate level question?

 

[sgnagni]

No problem. I am in a graduate program for secondary mathematics education in New York City. I'm in a "computers for mathematics teachers" course--we're learning to use Maple--and this is part of the first week's assignment.

Thanks for your input.

Steven

 

[sgnagni]

P.S. I do know how Pascal's triangle is constructed and how it is used in binomial expansions, but wasn't sure how to write this up in a proof.

Steven

 

[matt grime]

Well it would go something like.

0Cr is an integer, for all r (1 if r=0, and zero otherwise). Suppose that for a given n, all the nCr are integers, then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are integers for all r. Hence, by induction, nCr is an integer for all n and all r.

 

[robert Ihnot]

sgnagni:I do know how Pascal's triangle is constructed and how it is used in binomial expansions, but wasn't sure how to write this up in a proof.

Pascal's triange is a construction useful for getting ideas here, and some have used it for computation. But a proof that is algebraic is most likely based on algebraic considerations, as matt grime has shown.

 

[sgnagni]

Thanks

OK, thanks much to all. I think this gives me enough to proceed.

All best,
Steve

 

[mathwonk]

well there are n! ways toa rrange n thigns in a sequence. but one can accomplish this by first choosing a subset of r thigns from among the n thigns. then oine can arrange those r thigns in any order, followed by the remianing n-r thigns in any order.

since there are r! ways to order the r thigns and (n-r)! bways to arrangenr the n-r thigns, this gives the equation: number of ways to arrange n things = times number of ways to choose r of those things, times r! times (n-r)!

i.e. n! = nCr (r!)(N-r)!. that does it.

 

[matt grime]

but the OP specifically asked for an inductive proof.

 

[sgnagni]

Thanks again all. I did finish up that proof (even wrote it up in Maple!) and sent it off.

All best,
sgnagni

 

[soulflyfgm]

sgnagni i need to prove exactly the same thing u proved before. is there any way you could tell me how to start.? I am a little confuse ..please help

 

[Hurkyl]

Surely this thread has suggested places to start?

 

[soulflyfgm]

Well it would go something like.
0Cr is an integer, for all r (1 if r=0, and zero otherwise). Suppose that for a given n, all the nCr are integers, then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are integers for all r. Hence, by induction, nCr is an integer for all n and all r.

i am trying to prove that it would be a natural number. am i right in this prove?

nCr is n element of N for every o<= r<= n.
Suppose that a given r, all the nCr are nutural numbers
then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are natural numbers for all n. Hence, by inducion, nCr is a natural number for all n and all r.

can some one tell me if this prove is correct or can some one help me make it better?
thank you so much

 

[D H]

Well it would go something like.
0Cr is an integer, for all r (1 if r=0, and zero otherwise). Suppose that for a given n, all the nCr are integers, then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are integers for all r. Hence, by induction, nCr is an integer for all n and all r.

Nice trick, defining 0Cr as zero for all integral r but r=0.
If r is limited to the integers between 0 and n inclusive, the recursive relation {n+1}Cr = nCr + nC{r-1} doesn't generate {n+1}C{n+1} and {n+1}C0. One also needs to show that nC0 and nCn = 1 for all n >= 0. That's easy, but it does make the proof longer and the proof is no longer purely inductive. That neat trick, which is consistent with defining nCr using the gamma function, makes the proof purely inductive.

Edited to add

nCr is n element of N for every o<= r<= n.
Suppose that a given r, all the nCr are nutural numbers
then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are natural numbers for all n. Hence, by inducion, nCr is a natural number for all n and all r.
can some one tell me if this prove is correct or can some one help me make it better?
thank you so much

Two things are wrong with your proof.

First, you have to prove that the recursive relationship {n+1}Cr = nCr + nC{r-1} is valid. You stated it as a given.

Second, it has no basis. Any proof by induction that some predicate P is true for all integers n>=n0 has to have two parts: 1. Prove that P(n0) is true. 2. Prove that if P(k) is true then so is P(k+1). Your proof omits the first part.

matt grime establishes the basis very nicely by defining 0Cr as 1 if r = 0 and 0 for all other integers. This definition is consistent with the standard definition of 0C0. Matt's definition makes the proof purely inductive.

The definition is a subtle trick. Why is 0c1 = 0? What is 0c1? By the standard definition of nCr, 0c1 is 0!/(1!(-1)!), and (-1)! is not defined. Matt's definition is consistent with the analytic continuation of nCr to the gamma function: For example, 0c1 = gamma(1)/(gamma(1)*gamma(0)) = 0.

 

[soulflyfgm]

proof

Ok can i start something like this
Let P(n) be the statement that for any n in the natural numbers N, nCr is an element of N for every r with 0<= r<= n
nCr = n!/(r!(n-r)!)
0Cr = o!/(r!(0-r)!) = 0
so P(0)E(belongs) in N (natural numbers)
Suppose P(n) is a natural number of any N
then since {n+1}Cr = nCr + nC{r-1} is true ( already proved it algebraically and i will add it to this part) so it follows that the {n+1}Cr are natural numbers for all n. Hence, by inducion, nCr is a natural number for all n and all r.

can some one review this prove and tell me if its right? thank you so much for ur help

 

[soulflyfgm]

so am i right in this prove stated above?
anyone...thank you so much

 

[johnw188]

Well it would go something like.
0Cr is an integer, for all r (1 if r=0, and zero otherwise). Suppose that for a given n, all the nCr are integers, then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are integers for all r. Hence, by induction, nCr is an integer for all n and all r.

Haha, I wish I had happened across this a couple of weeks ago, this problem gave me quite some trouble. My proof ended up taking up about a page, in a much less elegant fashion, until I stumbled upon kind of the same idea. The thing that made it click for me was that kC0 = 1, because:

$$\frac{k!}{0! k!}$$

Likewise, (k+1)C0 = 1, and nCn = 1

After seeing that, the rest was trivial :)

 

[mathwonk]

Theorem: the following functions F(k,n) of two variables are all the same, for all k,n non negative integers:
1) n!/k!(n-k)!
2) the number of subsets of size k in a set of size n.
3) the coefficient of a^k b^(n-k) in the binomial expansion (a+b)^n.
4) the kth entry of the nth row of pascal's triangle. (numbering begins with 0 in both cases.)

proof: they all obey the same recursion relations, namely
(i) F(n,0) = 1 = F(n,n), for all n.

(ii) and F(k,n) = F(k,n-1) + F(k-1,n-1), for all k: 0<k<n, and all n.

 

[app_oos]

I understand that {n+1}Cr = nCr + nC{r-1}, but can someone tell me why it follows that {n+1}Cr are natural numbers just from that statement and the inductive hypothesis that nCr is all natural numbers?

 

[HallsofIvy]

Who said it did not depend on the inductive step? Since nCr and nC{r-1} are integers, {n+1}Cr is a sum of integers and so an integer.

 

[app_oos]

What I'm asking is, how do you show nC(r-1) is an integer?

 

[D H]

See post #13.

 

[app_oos]

Well it would go something like.

0Cr is an integer, for all r (1 if r=0, and zero otherwise). Suppose that for a given n, all the nCr are integers, then since {n+1}Cr = nCr + nC{r-1} it follows that the {n+1}Cr are integers for all r. Hence, by induction, nCr is an integer for all n and all r.

Ok, so he says that {n+1}Cr = nCr + nC{r-1}, which I understand. What I don't get is how it "follows" that {n+1}Cr is an integer as well, since you would need to show that both nCr and nC{r-1} are integers to use the closure property. We know the first one by assumption, but how do you know nC{r-1} is an integer, which wasn't explained in post 13?

 

[D H]

We know the first one by assumption, but how do you know nC{r-1} is an integer, which wasn't explained in post 13?

http://en.wikipedia.org/wiki/Mathematical_induction" .

 

[app_oos]

But you're trying to prove that any nCr will be an integer by induction. If you haven't proven it yet, then how can you say that nC(r-1) will be an integer?

 

[HallsofIvy]

But you're trying to prove that any nCr will be an integer by induction. If you haven't proven it yet, then how can you say that nC(r-1) will be an integer?

Are you saying you do not know what Mathematical Induction is?

To prove the statement P(n), some statement that depends on the positive integer n,
1) Prove that P(1) is true.
2) Prove that if P(k) is true then P(k+1) is true.

To prove, by induction, that P(n)= "_nC_r is an integer for all r between 0 and n":

1: ₁C₀ = ₁C₁= 1 so P(1) is true.

2: Assume that _kC[/sub]r[/sub] is an integer for some k and all r between 0 and k (the "Induction Hypothesis") and use the property mentioned, _k+1C_r= _kC_r+ _kC[/subr[/sub] to show that _k+1Cp_r is an integer.

Notice the difference between the "induction hypothesis" and what we are trying to prove: We are trying to prove that _nC_r is an integer for all positive integers n. The "induction hypothesis" is that _kC_r for some positive integer k. That's why I prefer to use "k" rather than n again but it really doesn't matter.

 

[D H]

But you're trying to prove that any nCr will be an integer by induction. If you haven't proven it yet, then how can you say that nC(r-1) will be an integer?

You are trying to prove {n+1}Cr is an integer by induction, not nCr.

Definitions:

• 0C0 = 1
• 0Cr = 0 for all real, non-zero r
• {n+1}Cr = nCr + nC{r-1}

Base case: 0Cr is an integer for all real r.
Proof: 0Cr is either zero or one by definition, both of which are integers.

Inductive step: If nCr is an integer for all real r, {n+1}Cr is an integer.
Proof: Assume nCr is an integer for all real r (that's how induction works). Using that {n+1}Cr = nCr + nC{r-1} by definition, {n+1}Cr is an integer for all real r since the sum of two integers is an integer and since nCr and nC{r-1} are both integers by assumption.

Therefore, nCr is an integer for all non-negative integers n by induction.