Stony Brook University
MAT 118 Spring 2013


Assignment 3 due in Recitation, week of February 18

Notes from class - this material is not in the text

Pascal's triangle $$\begin{array}{ccccccccccc} & & & & &1 & & & & & \\ & & & &1 & &1 & & & & \\ & & &1 & &2 & &1 & & & \\ & &1 & &3 & &3 & &1 & & \\ &1 & &4 & &6 & &4 & &1 & \\ 1 & &5 & &10 & &10 & &5 & & 1 \end{array}$$ This display shows rows 0, 1, 2, 3, 4, 5 of Pascal's triangle. The rows are constructed following two rules:
  1. Row $i$ has length $i+1$ and starts and ends with a $1$.
  2. Each interior element is the sum of the two above it.
We number the columns diagonally: column $0$ has all $1$s. Column $1$ reads $1, 2, 3, 4, 5, \dots$ . Column $2$ reads $1, 3, 6, 10, \dots$, etc.

The standard notation for the number in row $n$ and column $k$ is $\left ( \begin{array}{c} n\\k \end{array} \right )$. So $\left ( \begin{array}{c} n\\0 \end{array} \right )$ is always $1$, and $\left ( \begin{array}{c} n\\n \end{array} \right )$ is always $1$, whereas $\left ( \begin{array}{c} 5\\3 \end{array} \right ) = 10$.

The entries in Pascal's triangle appear in the Binomial Theorem: $$(a+b)^n = \left ( \begin{array}{c} n\\0 \end{array} \right ) a^n + \left ( \begin{array}{c} n\\1 \end{array} \right ) a^{n-1}b + \left ( \begin{array}{c} n\\2 \end{array} \right ) a^{n-2}b^2 + \dots + \left ( \begin{array}{c} n\\n-2 \end{array} \right ) a^2b^{n-2}+ \left ( \begin{array}{c} n\\n-1 \end{array} \right ) ab^{n-1} + \left ( \begin{array}{c} n\\n \end{array} \right ) b^n.$$
So for example $$(a+b)^0 = 1$$ $$(a+b)^1 = a+b$$ $$(a+b)^2 = a^2 + 2ab + b^2$$ $$\dots$$ $$(a+b)^5 = a^2 + 5ab^4 + 10a^2b^3 + 10 a^3b^2 + 5a^4b + b^5.$$

You can check that $$(1+1)^5 = 1 + 5 + 10 + 10 + 5 + 1$$ or $2^5 = 32$. More generally, a similar calculation shows that the sum of the numbers in row $n$ is $2^n$. Make sure you understand why this follows from the Binomial Theorem.

Pascal's triangle and the Sierpinski triangle

Suppose in Pascal's triangle we replace all odd numbers by $1$ and all even numbers by $0$. We get (writing the columns vertically instead of diagonally for typographical convenience):

$1$
$1$$1$
$1$$0$$1$
$1$$1$$1$$1$
$1$$0$$0$$0$$1$
$1$$1$$0$$0$$1$$1$
$1$$0$$1$$0$$1$$0$$1$
$1$$1$$1$$1$$1$$1$$1$$1$
$1$$0$$0$$0$$0$$0$$0$$0$$1$
$1$$1$$0$$0$$0$$0$$0$$0$$1$$1$
$1$$0$$1$$0$$0$$0$$0$$0$$1$$0$$1$
$1$$1$$1$$1$$0$$0$$0$$0$$1$$1$$1$$1$
$1$$0$$0$$0$$1$$0$$0$$0$$1$$0$$0$$0$$1$
$1$$1$$0$$0$$1$$1$$0$$0$$1$$1$$0$$0$$1$$1$
$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$
$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$
etc.

Notice that the triangle formed by the first 16 rows (number 0 to 15) contains three smaller triangles of height 8 and of the form:

$1$
$1$$1$
$1$$0$$1$
$1$$1$$1$$1$
$1$$0$$0$$0$$1$
$1$$1$$0$$0$$1$$1$
$1$$0$$1$$0$$1$$0$$1$
$1$$1$$1$$1$$1$$1$$1$$1$

and that each of them contains three triangles of height 4 and of the form:

$1$
$1$$1$
$1$$0$$1$
$1$$1$$1$$1$

and that each of those contains three triangles of height 2 and of the form:

$1$
$1$$1$

and that each of them contains three "triangles" of height 1!

Exercise 1.

So the $(0,1)$ Pascal triangle with 16 rows corresponds to step 4 in the generation of the Sierpinski triangle. How many rows will it take to get a configuration corresponding to step 5? Explain your answer carefully. Draw a picture if necessary.

Exercise 2.

Using the Binomial Theorem, show that the alternating sum of the elements in any row of Pascal's original triangle is $0$. For example $1 - 4 + 6 - 4 + 1 = 0$. [alternating means that you alternate addition and subtraction].

Exercise 3.

Suppose instead of replacing the numbers in Pascal's triangle by $0$ or $1$ depending on their parity (odd or even) we replace them by their remainders when divided by $3$. So the new entries will be $0$, $1$, or $2$. The table starts:

1
11
121
1001
11011
121121
1002001
11022011
121212121
1000000001
etc.

Note that the entries in this table can be calculated directly using addition modulo 3: \begin{array}{c|ccc} +&0&1&2\\\hline 0&0&1&2\\ 1 &1&2&0\\ 2&2&0&1 \end{array} Can you see a Sierpinski-like process here? Explain. Tell as much about it as you can. Feel free to calculate additional rows!

Exercise 4.

Suppose that instead of defining the binomial coefficients from Pascal's triangle, we define them by the equation: $$\left ( \begin{array}{c} n\\k \end{array} \right ) = \frac{\displaystyle n!} {\displaystyle k! (n-k)!}$$ where $n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot 3\cdot 2\cdot 1$ is the product of all the integers from $1$ to $n$, and $0! =1! =1$.

Check that this definition also gives $\left ( \begin{array}{c} 5\\3 \end{array} \right ) = 10$.

Show that the coefficients defined using this definition satisfy: $$\left ( \begin{array}{c} n+1\\k+1 \end{array} \right ) = \left ( \begin{array}{c} n\\k \end{array} \right ) + \left ( \begin{array}{c} n\\k+1 \end{array} \right ).$$ Hint: put the terms on a common denominator.

Remember: Collaboration is fine, but what you hand in must be in your own words. Handing in something you copied is plagiarism and will cost you if it is detected. Write down what you tried and how it worked.

Hand in your work at the recitation meeting (Mon, Wed or Thur) next week.