MA-351, Fall 2022, Homework 1
Due as indicated for each problem.

All solutions must be submitted on the Moodle web site for the class at wolfware.ncsu.edu. You may upload a photo of your handwritten solution or a file of your typed solution.
Note my office hours on my schedule.

1. Due Sep 8, 2022, 11:59pm.
   Consider the sequence g₀ = 1, g₁ = 1, g₂ = 9, g₃ = 41, g₄ = 209, g₅ = 1041, g₆ = 5209,... whose linear generator is g_n+2 = 4g_n+1 + 5g_n.
   1. As we did for the Fibonacci numbers, please derive a closed form expression for g_n.
   2. Consider the sequence h_n = g_n + g_n+1: 2,10,50,250,1250,6250,... Please give a first order homogeneous linear recurrence with constant coefficients for h_n and prove that your recurrence is correct for all n.

2. Due Sep 14, 2022, 11:59pm
   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.
   
   
3. Due Sep 14, 2022, 11:59pm
   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.