# Proof by induction: nCr always an integer

1. Jan 30, 2005

### 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.

Best regards,
SG

2. Jan 30, 2005

### Hurkyl

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

3. Jan 30, 2005

### sgnagni

Re: Proof

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

4. Jan 30, 2005

### Hurkyl

Staff Emeritus
So what definition of nCr are you using?

5. Jan 30, 2005

### sgnagni

Proof: nCr

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

Steve

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

6. Jan 30, 2005

### Hurkyl

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

7. Jan 30, 2005

### sgnagni

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

And then what would I take as my induction hypothesis?

Steve

8. Jan 30, 2005

### Hurkyl

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

9. Jan 30, 2005

### sgnagni

Would I do it as some sort of a matrix?

Steve

10. Jan 31, 2005

### 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?

11. Jan 31, 2005

### sgnagni

Re: Proof

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.

Steven

12. Jan 31, 2005

### sgnagni

Re: Proof

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

13. Jan 31, 2005

### 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.

14. Jan 31, 2005

### 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.

15. Feb 1, 2005

### sgnagni

Thanks

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

All best,
Steve

16. Feb 1, 2005

### 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.

17. Feb 2, 2005

### matt grime

but the OP specifically asked for an inductive proof.

18. Feb 6, 2005

### sgnagni

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

All best,
sgnagni

19. Nov 18, 2005

### soulflyfgm

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

20. Nov 18, 2005

### Hurkyl

Staff Emeritus
Surely this thread has suggested places to start?