MA-351 Homework 1
Due at 4:59pm in my mailbox in HA 245, Thursday, September 13, 2007
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.
Note my office hours on my schedule.
-
Consider the linear recurrence
gn = -gn-1 + gn-2
for all n > 1
with the initial conditions
g0 = 1, g1 = 0.
- Derive a "closed form" solution for the above
recurrence.
- Prove that gn = (-1)nfn-2
for all n > 1
where fn are the Fibonacci numbers with
f-1 = 0, f0 = 1.
- Prove that the number of edges in the n-dimensional
hypercube is n 2n-1.
- 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.
- Draw a nice picture of the digraph for r = 3.
- 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.