# Recursive relationships

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 ad1c9bdddfhttps://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.