MA-351 Homework 1

Due at 4:59pm in my mailbox in HA 245, Monday, September 11, 2006

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.

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 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 5-digit binary numbers (sequences of 5 integers from 0 and 1) in such a way that the Hamming distance between adjacent vertices is exactly one.