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