MA-351 Homework 1

Due at 9:50am, Tuesday, September 9, 2003

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).

1. Consider the Fibonacci numbers f₀=1, f₁=1 such that f_i+2 = f_i+1 + f_i is satisfied for any integer i. For i ≥ 0 we have the Fibonacci numbers from class, but it is possible from the recursion to determine uniquely the numbers with negative subscripts.
   1. Please write down the numbers f_-1, f_-2, f_-3, f_-4, f_-5, f_-6, f_-7.
   2. If by g_k we denote f_-k for k ≥ 0, please write a linear recursion for g_k+2.
   3. Following the procedure from class, from the recursion given in b. and the initial values in a., please compute a closed form formula for g_k.

2. Prove that the number of edges in the n-dimensional hypercube is n 2^n-1.

3. Consider the n-dimensional de Bruijn digraph with 2ⁿ vertices and 2ⁿ⁺¹ arcs. Like in the hypercube, the vertices are n-bit numbers. There is an arc from each vertex denoted by i₁,i₂,...,i_n, where i_j is either 0 or 1, to the vertex denoted by i₂,i₃,...,i_n,0 and an arc to the vertex denoted by i₂,i₃,...,i_n,1.
   1. Draw a nice picture of the digraph for n = 3.
   2. Prove that for n = 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.
   3. For arbitrary n, what is the maximal indegree among all of the vertices? Please explain.