MA-351 Homework 1

Due at 9:50am in class, Tuesday, September 7, 2004


Calculations necessary for these problems may be done either by hand or with Maple. Solutions may be submitted in person in class, or you may email an ASCII text, Maple Worksheet (.mws), html, or postscipt/pdf-formatted document to me (kaltofen@math.ncsu.edu).
Note my office hours on my schedule. I will also be available tomorrow from 12:00-13:00.

    1. Derive the linear recurrence for Fibonacci's rabbits' problem with the change that each pair of rabbits gives birth to two pairs of rabbits instead of one.
    2. Derive a "closed form" solution for the above recurrence.

  2. Prove that the number of edges in the n-dimensional hypercube is n 2n-1.
  3. Consider the r-dimensional de Bruijn digraph with 2r vertices and 2r+1 arcs. Like in the hypercube, the vertices have r subscripts that are either 0 or 1. There is an arc from each vertex subscripted by i1,i2,...,ir, where ij is either 0 or 1, to the vertex subscripted by 0,i1,i2,...,ir-1 and an arc to the vertex subscripted by 1,i1,i2,...,ir-1.
    1. Draw a nice picture of the digraph for r = 3.
    2. Prove that for r = 4 the digraph has the same diameter as the 4 dimensional hypercube, that is, the maximum distance between two vertices is 4. Your argument must both show that between any two vertices there is a path of length no more than 4, and that there exist two vertices whose distance is at least 4.