Math 301: Homework 4

Due: Friday, September 27, 2019

Reading: Read sections 3.1, 3.2, 3.3, 3.4, 3.5, and 3.6.

Exercises:

  1. Find the exact coefficient of \(a^{314}b^{876}\) in \((1 + a + b)^{2019}\).

    This is a multinomial question. We have 2019 factors, and in each we may choose either a \(1\), an \(a\), or a \(b\). To get a term \(a^{314}b^{876}\), we must choose 314 \(a\)’s, and from the remainder 876 \(b\)’s. Hence the answer is

    \[ \binom{2019}{314, 876, (2019-314-876)}. \]

    Challenge: Can you find the answer using the binomial theorem on \((1 + (a+b))^{2019}\)?

  2. How many ways can you distribute \(100\) identical quarters to \(8\) people if each person is supposed to get at least \(3\) quarters?

    Here is one way to solve this. First, distribute 3 quarters to each of the 8 people, using up 24 of our 100 quarters. There is only 1 way to do this! We now have 76 quarters left to distribute, and there are no rules about how many quarters everyone gets. So the answer is

    \[ \binom{76 + 8 - 1}{8 - 1} \]

  3. Recall from Calculus that, for any \(k, m \in \mathbb N\):

    \[\frac{d^k}{dx^k} x^m = \left\{ \begin{array}{lr} \frac{m!}{(m-k)!}x^{m-k} & m \ge k \\ 0 & \textrm{otherwise} \end{array} \right.\]

    Let \(f(x) = (1 + x)^n\). Show that \[\frac{f^{(k)}(0)}{k!} = \binom nk.\] (Remember that \(f^{(k)}\) is the \(k\)th derivative of \(f\)).

    By chain rule on the LHS, we see that \(\frac {d^k}{dx^k}(1 + x)^n = \frac{n!}{(n-k)!}(1+x)^{n-k}\). Plugging in \(x = 0\) and dividing by \(k!\) yields exactly the formula for \(\binom n k\).

    Remark: In general, \(\frac{f^{(k)}(0)}{k!}\) is the coefficient of \(x^k\) in the power series of \(f\).

    1. Write out the first 20 rows of Pascal’s even/odd triangle: The shape is the same as in Pascal’s triangle, but write a 0 if the entry in Pascal’s triangle was even, or a 1 if the entry was odd. For example, the first few rows are:

             1     
            1 1    
           1 0 1   
          1 1 1 1  
         1 0 0 0 1 
        1 1 0 0 1 1
      

      Hint: Do you need to compute every binomial coefficient to do this?

    2. Do you see any patterns? Describe them (with words or pictures).

    3. Next to each row, write out its sum. Which rows are completely odd? Challenge: Can you think of a formula for the sums? (I don’t know an easy formula. Try using words, or describe it recursively.)

    1. We don’t have to write out the whole Pascal’s triangle beforehand; we can just use the rule that “even+even=odd”, “even+odd=odd”, and “odd+odd=even” to fill out the triangle.

    2. We see something reminiscent of the Sierpinski triangle.

    3. The rows that consist entirely of odds are the rows of the form \(2^m - 1\). In general, if \(b(n)\) is the number of 1’s in the binary expansion of \(n\) the formula for the sums of the rows is \(2^{b(n)}\).

  4. Explain why, for \(k,m \in \mathbb N\): \[ \binom 0k + \binom 1k + \binom 2k + \cdots + \binom mk = \binom{m+1}{k+1}. \]

    Notice that by their counting definition, \(\binom rk = 0\) for all \(r < k\). So the statement to prove becomes,

    \[ \binom kk + \binom {k+1}k + \binom {k+2}k + \cdots + \binom mk = \binom{m+1}{k+1}. \]

    Now by applying the symmetry property of binomial coefficients, this statement is equivalent to,

    \[ \binom k0 + \binom {k+1}1 + \binom {k+2}2 + \cdots + \binom m{m-k} = \binom{m+1}{m-k}. \]

    Making the change of variables \(n = k\) and \(h = m-k-1\) this is equivalent to,

    \[ \binom n0 + \binom {n+1}1 + \binom {n+2}2 + \cdots + \binom {n+h+1}{h+1} = \binom{n+h+2}{h+1}, \]

    which is exactly an identity we proved in class. So all of these equalities hold, in particular, the statement to be shown holds!