Proof by induction: nCr always an integer

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

 

[app_oos]

since nCr and nC{r-1} are both integers by assumption.

This is the only part I don't get. I know nCr was assumed to be an integer (induction hypothesis) but where was nC(r-1) assumed to be an integer? Is this some sort of axiom, that if nCr is an integer, then nC(r-1) is one too? I understand the other parts of the proof and I know what induction is, by the way.

 

[D H]

This is the only part I don't get. I know nCr was assumed to be an integer (induction hypothesis) but where was nC(r-1) assumed to be an integer?

If nCr is an integer for all real r, then so is nC{r-1} because r-1 is a real.

 

[HallsofIvy]

Well, for all positive integers r. nCr is only defined for n and r positive integers.

 

[D H]

Well, for all positive integers r. nCr is only defined for n and r positive integers.

The point of this thread is to extend to the concept nCr to real r. The constraint that n be a non-negative integer, true.