using 12 prove that sigma n r 0 rn r n2n1 Why is this resul

using (1.2), prove that sigma n r =0 r(n r) = n2^n-1. Why is this result obvious when we consider the average size of a subset of a set of n elements? Theorem 1.2 The number of ways of selecting r objects from n, in order but with no repetitions, is

Solution

P(n,r) = n! / [ r! * (n-r)! ]

P(n , r-1) = n! / [ (r-1)! * (n-r+1)! ]
add them
n! / [ r! * (n-r)! ] + n! / [ (r-1)! * (n-r+1)! ] =
and we know
(n-r+1)! = (n-r+1) * (n-r)! also r!= r * (r-1)! so we have

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

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

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

[ n! * (n+1) ] / [ r * (r-1)! * (n-r)! * (n-r+1) ] =
replace them again
(n+1)! / [ r! * (n-r+1)!