MA-351 Homework 1 (FINAL VERSION: 3 PROBLEMS)

Due at 9:50 in class, Tuesday, August 31, 1999

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. 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 2^n-1.
3. Consider the following graph: V = {v_i,a,b,c}, where i = 0,1,2,3 (the level) and a,b,c is either 0 or 1. There are the following edges in the graph:
   • {v_i,a,b,c, v_i+1,a,b,c} for i = 0,1,2 and all a,b,c.
   • {v_0,0,b,c, v_1,1,b,c}, {v_0,1,b,c, v_1,0,b,c} for all b,c.
   • {v_1,a,0,c, v_2,a,1,c}, {v_1,a,1,c, v_2,a,0,c} for all a,c.
   • {v_2,a,b,0, v_3,a,b,1}, {v_2,a,b,1, v_3,a,b,0} for all a,b.
   1. Draw a nice picture of the graph. [Hint: on each level show the nodes of subscript abc in the order 000, 001, 010, 011, 100, 101, 110, 111. The graph is called a butterfly.]
   2. Prove that any two vertices v_0,a,b,c and v_3,a',b',c', where a,b,c,a',b',c' in {0,1}, are connected by a unique shortest path of length 3.