Exercise 10

Calculating the binomial coefficients we find out that if  k  is an odd number then the coefficient is  0.  If  k is even number between -50 and 50, then the coefficient is Binomial[100, (100-k)/2]. Test

{Coefficient[Expand[(((x + (1/x)))^100)], (x^4)], 
      Binomial[100, (100 - 4)/2]}

{Coefficient[Expand[(((x + (1/x)))^100)], (x^18)], 
      Binomial[100, (100 - 18)/2]}

To verify all the coefficients I use

Expand[(((x + (1/x)))^100)]

However, to get coefficients I have to turn the expression into a polynomial. Here is a smaller example

Expand[(x^10) (((x + (1/x)))^10)]

CoefficientList[(x^10) Expand[(((x + (1/x)))^10)], x]

Table[{CoefficientList[Expand[(x^100) (((x + (1/x)))^100)], 
            x][[2 (j + 50 + 1) - 
            1]], Binomial[100, 50 - j]}, {j, -50, 
        50}]

Or, even better,

Table[CoefficientList[Expand[(x^100) (((x + (1/x)))^100)], 
            x][[2 (j + 50 + 1) - 
            1]] - Binomial[100, 50 - j], {j, -50, 
        50}]

Exercise 14

We will prove that  Binomial[n,Floor[n/2]] = Binomial[n,Ceiling[n/2]].

First check the first few terms.

Table[{Binomial[n, Floor[n/2]], Binomial[n, Ceiling[n/2]]}, {n, 1, 
        20}]

If  n is even, then n  =  2 k for some positive integer k. In this case Floor[n] = Ceiling[n] = k.

If  n is odd, then n  =  2 k - 1 for some positive integer k. In this case Floor[n] = k-1 and Ceiling[n] = k.  Since for every j Binomial[n,j] = Binomial[n, n-j], we have Binomial[n,k-1] = Binomial[n, n-k+1] = Binomial[n, 2 k-1 -k+1] = Binomial[n, k].

Next, let  1≤ k < Floor[n/2].  Then 2k < 2 Floor[n/2].  Consequently,  2k+1 ≤ 2 Floor[n/2]. Since these two numbers can not be equal (one is even, the other odd), we have 2k+1 < 2 Floor[n/2]. Clearly  2 Floor[n/2] ≤ n, and thus  2 k + 1 < n.  This yields, k+1 < n-k, and hence

(1/(k + 1)) >  (1/(n - k)).

Multiplying both sides by   ((n!)/(k! (n - k - 1)!))  we get  \(TraditionalForm\`\(n!\)\/\(\(\((k + 1)\)!\) \(\((n - k - 1)\)!\)\) > \ \(n!\)\/\(\(k!\)\ \(\((n - k)\)!\)\)\),  that is  Binomial[n,k+1] > Binomial[n,k].

Exercise 15

The number Binomial[n,k] represents the number of bit strings of length n with exactly k zeros. The number (2^n) represents the number of all bit strings of length n. Thus the inequality.

Exercise 16

Table[{N[Binomial[n, Floor[n/2]], 2], N[(2^n)/(n), 2]}, {n, 2, 
        100}]

First notice that  for  n ≥ 2  we have Binomial[n,Floor[n/2]] ≥ Binomial[n,0] + Binomial[n,1].  Therefore

(2^n)=(∑_(k = 0)^n)(({{n}, {k}})) = (({{n}, {0}}))+(({{n}, {n}}))+(∑_(k = 1)^(n - 1))(({{n}, {k}})) ≤ (({{n}, {Floor[n/2]}}))+(n - 1)(({{n}, {Floor[n/2]}}))=n (({{n}, {Floor[n/2]}}))

Exercise 22

This is counting number of committees with a subcommittees. For example the university faculty elects the faculty senate, then the senate elects its executive committee.  If there are  n  faculty members, the senate has r members and the executive committee of the senate has k members count number of different ways of forming the senate with its executive committee.

One way of counting: Choose the senate, then choose the executive committee from the senate. By the product rule there are Binomial[n,r]*Binomial[r,k] ways to do this.

Another way of counting is: choose the executive committee from the whole faculty, then choose the remaining members of the senate. By the product rule there are  Binomial[n,k]*Binomial[n-k,r-k]  ways to do this.

Since we count the same set these two numbers must be equal.

Exercise 25

A combinatorial way to prove this identity is to look at  a  class of  2n males and  2 females and count the number of committees of n+1 members that can be formed.  There are Binomial[2n+2,n+1] such committees.

Now we count the number of committees based of number of female members.

There are Binomial[2n,n+1]  committees with no female members,  there are  2 Binomial[2n,n]  with one female member and thee are Binomial[2n,n-1] committees with two female members. Since  Binomial[2n,n-1] = Binomial[2n,n+1], the formula follows.

Exercise 26

The formula

(∑_(k = 1)^n)(({{n}, {k}})) (({{n}, {k - 1}}))=(∑_(k = 1)^n)(({{n}, {k}})) (({{n}, {n + 1 - k}}))= (({{2  n}, {n + 1}}))

since both sides count the number of committees with n+1 memberf from a class of  2n people. In the sum we assume that there are n males and n females and then count the committees with 1, 2, 3, ..., n  males.

Now we need to prove

(({{2  n}, {n + 1}})) +(({{2  n}, {n}})) = (({{2  n + 2}, {n + 1}}))/2

or, simpler,

(({{2  n + 2}, {n + 1}})) = 2(({{2  n}, {n + 1}})) +2 (({{2  n}, {n}}))

This can be proved by using Pascal's identity twice

(({{2  n + 2}, {n + 1}})) = (({{2  n + 1}, {n + 1}}))+(({{2  n + 1}, {n}})) =(({{2  n}, {n + 1}}))+(({{2  n}, {n}}))+(({{2  n}, {n}})) +(({{2  n}, {n - 1}}))  =(({{2  n}, {n + 1}})) +2 (({{2  n}, {n}}))+(({{2  n}, {2  n - (n - 1)}})) =2(({{2  n}, {n + 1}})) +2 (({{2  n}, {n}}))