MA-351, Fall 2024, 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 Thurs Sep 5, 2024, 11:59pm.
   Consider the sequence g₀ = 0, g₁ = 1, g₂ = 1/2, g₃ = 13/36, g₄ = 17/72, g₅ = 205/1296, g₆ = 91/864, g₇ = 3277/46656,... whose linear generator is g_n+2 = g_n+1/2 + g_n/9, that is, the next element is a (1/2,1/9)-weighted sum of the previous two.
   1. As we did for the Fibonacci numbers, please derive a closed form expression for g_n.
   2. Consider the sequence h_n = 6^n–1 g_n: 0, 1, 3, 13, 51, 205, 819, 3277,... Please give a second order homogeneous linear recurrence with constant coefficients for h_n and prove that your recurrence is correct for all n. The recurrence proves 6^n–1 g_n are integers.

2. Due Wed Sep 11, 2024, 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 Wed Sep 11, 2024, 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.