+0  
 
0
23
2
avatar

Help with these hard counting

 

Let n be a positive integer.  Let k be a positive integer.

 

(a) Using a counting argument, show that C(n - 1, k - 1) + C(n - 1, k) = C(n,k).

 

(b) Using a counting argument, show that C(n,0) + C(n,1) + C(n,2) + ... + C(n,n) = 2^n.

 

(c) Using a counting argument, show that C(n,0) + C(n + 1,1) + C(n + 2,2) + C(n + 3,3) + ... + C(n + k,k) = C(n + k + 1,k)

 

(d) Using a counting argument, show that C(m,0) C(n,r) + C(m,1) C(n,r - 1) + ... + C(m,r) C(n,0) = C(m + n,r).

 

(e) There are n^2 ordered pairs (a,b) of positive integers, where 1 \le a, b \le n.  Using a counting argument, show that this number is also equal to
(n + 1)^2 - 2n - 1

 

(f) There are n^3 ordered triples (a,b,c) of positive integers, where 1 \le a, b, c \le n.  Using a counting argument, show that this number is also equal to
(n + 1)^3 - 3n^2 - 3n - 1

 
 Jan 24, 2023
 #1
avatar+2532 
+1

a)

 

 Note that \({n - 1 \choose k - 1} = {(n-1)! \over (k-1)! (n-k)!}\) and \({n -1 \choose k} = {(n-1)! \over {k! (n-k-1)!}}\)

 

The LCD of both denominators is \(k!(n-k)!\). To get this, multiply the first denominator by k and the second denominator by n -k.

 

This gives us \({k(n-1)! \over k!(n-k)!} + {(n-k)(n-1)! \over k!(n-k)!} = {(n-k)(n-1)! + k(n-1)! \over k!(n-k)}\)

 

Now, factor the numerator into \((n-k+k)(n-1)! = n(n-1)! = n!\)

 

This leaves us with \({n! \over k!(n-k)!} = {n \choose k}\)

 
 Jan 24, 2023
 #2
avatar
0

Now do the rest

 
Guest Jan 24, 2023

28 Online Users