MA-351 Homework 1

Due at 4:59pm in my mailbox in SAS 3151, Thursday, September 6, 2012

All solutions must be submitted in hardcopy either to me in class or placed in my mailbox. Note my office hours on my schedule.

1. Consider the sequence g₀ = 1, g₁ = 1, g₂ = 3, g₃ = 5, g₄ = 11, g₅ = 21, g₆ = 43, g₇ = 85,... whose linear generator is g_n+2 = g_n+1 + 2g_n.
   1. As we did for the Fibonacci numbers, please give closed form expression for g_n.
   2. Please give a closed form expression for the sum g₀ + g₁ + ... + g_n as well.

2. Consider the r-dimensional de Bruijn digraph with 2^r vertices and 2^r+1 arcs. Like in the hypercube, the vertices are strings of r bits. There is an arc from each vertex i₁,i₂,...,i_r, where i_j is either 0 or 1, to the vertex 0 i₁,i₂,...,i_r-1 and an arc to the vertex 1 i₁,i₂,...,i_r-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.

3. Consider the 5-dimensional hypercube as presented in class. In class the vertices were the integers from 1 to 32. The task is to relabel the vertices in the drawing as strings of 5 bits (5-bit binary numbers) in such a way that the Hamming distance between adjacent vertices is exactly one.