Explore BrainMass

Explore BrainMass

    Recursive relationships

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Consider the recursive relationship for combinations:

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

    Prove this relationship algebraically using the mathematical definition of a combination, as well as that of the factorial function.

    Provide a logical explanation for this relationship (Hint: consider n objects as consisting of n-1 existing objects plus a new nth object. Given the ultimate goal of selecting r objects from the entire set of n, you must select objects from the set of n-1 objects and decide how the new nth object should join the existing selected sets.)

    © BrainMass Inc. brainmass.com November 24, 2021, 11:20 am ad1c9bdddf
    https://brainmass.com/math/discrete-structures/recursive-relationships-22833

    Solution Preview

    Because, C(n,r) = n!/(r!*(n-r)!)
    RHS:
    C(n-1,r) + C(n-1,r-1)
    = {(n-1)!/(r!*(n-1-r)!)} + {(n-1)!/((r-1)!*(n-r)!}
    = {(n-1)!/((r-1)!*(n-r-1)!)} * { (1/r) + (1/(n-r))}
    (Because, (n-r)! = (n-r-1)!*(n-r); r! = (r-1)!*r)

    = {(n-1)!/((r-1)!*(n-r-1)!)} * {(n-r + ...

    Solution Summary

    This solution shows a simple proof regarding recursive relationships. It is solved in step by step format.

    $2.49

    ADVERTISEMENT