How do you prove C(n + 1, r + 1) = C(n, r) + C(n, r + 1)?

Question

Update:

Thank you everyone for your kind answers.

Answer 1

Favorite Answer

c(a , b) = a! / (b! * (a - b)!)

C(n + 1 , r + 1) =>

(n + 1)! / ((r + 1)! * ((n + 1) - (r + 1))!) =>

(n + 1)! / ((r + 1)! * (n + 1 - r - 1)!) =>

(n + 1)! / ((r + 1)! * (n - r)!)

C(n , r) =>

n! / (r! * (n - r)!)

C(n , r + 1) =>

n! / ((r + 1)! * (n - r - 1)!) =>

n! / ((r + 1) * r! * (n - r)! / (n - r)) =>

n! * (n - r) / ((r + 1) * r! * (n - r)!) =>

(n - r) / (r + 1) * (n! / (r! * (n - r)!))

(1 + (n - r) / (r + 1)) * (n! / (r! * (n - r)!)) =>

((r + 1 + n - r) / (r + 1)) * (n! / (r! * (n - r)!)) =>

((n + 1) / (r + 1)) * (n! / (r! * (n - r)!)) =>

(n + 1) * n! / (r! * (r + 1) * (n - r)!) =>

(n + 1)! / ((r + 1)! * (n - r)!)

• A

  Lv 4

  11 months agoReport

  Very nice!
  

Answer 2

For example , think there are n students and 1 teacher .

Clearly C(n+1,r+1) ways exist to choose r+1 persons .

These C(n+1,r+1) ways can be divided into 2 groups ,

"include the teacher" and "exclude the teacher" .

The number of the former ways is C(n,r) because we must choose r students

out of n students .

The number of the latter ways is C(n,r+1) because we must choose r+1 students

out of n students .

Therefore , C(n+1,r+1) = C(n,r) + C(n,r+1) .

Answer 3

What is the number C(n+1, r+1) of (r+1)-element subsets that an (n+1)-element set S has?

Let's fix an element x of S and separately count those (r+1)-element subsets of S that don't have x as an element and those that do:

1. The number of (r+1)-element subsets of S to which x ::doesn't:: belong is C(n, r+1), because that's the number of (r+1)-element subsets of S \ {x}.

2. The number of (r+1)-element subsets of S to which x ::does:: belong is C(n, r), because that's the number of r-element subsets of S \ {x}.

Thus C(n+1, r+1) = C(n, r+1) + C(n, r).

Answer 4

C(n + 1, r + 1) = (n+1)! / ( (r+1)! (n-r)! )

C(n + 1, r + 1) = (n+1)! / ( (r+1)! (n-r)(n-(r+1)! )

C(n + 1, r + 1) = (1/(n-r)) (n+1)n! / ( (r+1)! (n-(r+1)! )

C(n + 1, r + 1) = ((n+1)/(n-r)) n! / ( (r+1)! (n-(r+1)! )

C(n + 1, r + 1) = ((r+1 + n-r)/(n-r)) n! / ( (r+1)! (n-(r+1)! )

C(n + 1, r + 1) = ((r+1)/(n-r) + 1) n! / ( (r+1)! (n-(r+1)! )

C(n + 1, r + 1) = ((r+1)/(n-r)) n! / ( (r+1)! (n-(r+1)! ) + n! / ( (r+1)! (n-(r+1))! )

C(n + 1, r + 1) = (r+1) n! / ( (r+1)r! (n-r)(n-(r+1)! ) + n! / ( (r+1)! (n-(r+1))! )

C(n + 1, r + 1) = n! / ( r! (n-r)! ) + n! / ( (r+1)! (n-(r+1))! )

C(n + 1, r + 1) = C(n, r) + C(n, (r+1))

Answer 5

look at C(n+1,r+1) - C(n, r+1) = C(n , r )...easier to see the left = the right

Answer 6

From the right side

C(n, r) + C(n, r + 1) = n!/(r!(n-r)!)+n!/((r+1)!(n-r-1)!) = n![(r+1)+(n-r)]/[(r+1)!(n-r)!]=n!(n+1)/[(r+1)!(n-r)!] = (n+1)!/[(r+1)!(n-r)!] = C(n + 1, r + 1)

Answer 7

could be

Answer 8

rorsdgbr

Answer 9

fswlmgst

Answer 10

you did it!