A
Lv 4
A asked in Science & MathematicsMathematics · 11 months ago

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

Update:

Thank you everyone for your kind answers.

11 Answers

Relevance
  • 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)!)

  • atsuo
    Lv 6
    11 months ago

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

  • jibz
    Lv 6
    11 months ago

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

  • 11 months ago

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

  • How do you think about the answers? You can sign in to vote the answer.
  • ted s
    Lv 7
    11 months ago

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

  • alex
    Lv 7
    11 months ago

    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)

  • Anonymous
    11 months ago

    could be

  • Anonymous
    11 months ago

    rorsdgbr

  • Anonymous
    11 months ago

    fswlmgst

  • 11 months ago

    you did it!

Still have questions? Get your answers by asking now.