Recurrence relation for n-cube

Question

For a natural number n, the n-cube is a figure created by the following recipe. The 0-cube is simply a point. For n>0, we construct an n-cube by taking two disjoint copies of an (n-1)-cube and then joining corresponding points in the two cubes by line segments. Thus, a 1-cube is simply a line segment and a 2-cube is a quadrilateral. The figure shows the construction of a 4-cube from two copies of a 3-cube. Note that an n-cube has twice as many points as an (n-1)-cube; therefore, an n-cube has $2^n$ points. The questions is, how many line segments does an n-cube have? Let $a_n$ denote the number of line segments in an n-cube. We have $a_0 = 0, a_1 = 1, a_2 = 4, a_3 = 12, \text{ and } a_4 = 32$.
a. Calculate $a_5$
b. Find a formula for $a_n$ in terms of $a_n-_1$
c. Find a formula for $a_n$ just in terms of n (and not in terms of $a_n-_1$) and use part (b) to prove that your formula is correct.

I am trying to self teach myself recurrence relations but I am stuck on this question. A clear explanation would be appreciated.

Answer 1

Regard the figure showing the construction of a 4-cube from two copies of the 3-cube. How do line segments arise in the 4-cube? There are three types:

• each line segment in the first 3-cube
• each line segment in the second 3-cube
• for every point (vertex) of the first 3-cube, a new line segment connecting it to its twin in the second 3-cube

Of course, a similar description holds for any $(n+1)$-cube constructed from a pair of $n$-cubes.

You should be able to use this description (and the known formula for the number of points in the $n$-cube) to write down a recurrence relation for $a_n$.

Answer 2

A vertex $a$ in $n$ cube is of the form $$(a_1,a_2,a_3,\ldots,a_n)$$ where $a_k \in \{0,1\}$. Two vertices $a$ and $b$ are neighbors, i.e., they share an edge, if $b_j = a_j$ for all $j$'s except for one $j$. Hence, for each vertex there $n$ neighbors. The total number of vertices in a $n$ cube is $2^n$. Hence, the total number of edges is $n \cdot 2^n$. But this involves double counting since each edge is shared by $2$ vertices. Hence, the total number of edges is $$n \cdot 2^{n-1}$$

Answer 3

a. Note that a 5-cube is constructed from two 4-cubes where we join their vertices together. So it contains $a_4$ edges from the first 4-cube, $a_4$ edges from the second 4-cube and $2^4$ edges from each vertex. So in total:$$ a_5 = 2a_4 + 16 = 80$$

b. Since there was nothing special about $5$, we can use the same reasoning for any $n$-cube, we get that $$a_n = 2a_{n-1}+2^{n-1} $$

c. First we notice by trial and error, that $$a_0 = 0 = 2^{-1}*0$$ $$a_1 = 1 = 2^{1-1}*1$$ $$a_2 = 4 = 2^{2-1}*2$$ $$a_3 = 12 = 4*3 = 2^{3-1}3$$ $$a_4 = 32 = 8*4 = 2^{4-1}4$$

We guess that $a_n = 2^{n-1}n$, we can show this by induction:

Base Case: $a_0 = 0 = 2^{-1}*0$

Inductive hypothesis: if this is true for $a_{n-1}$ then we have: $$ a_n = 2a_{n-1}+2^{n-1} = 2*(2^{n-2}(n-1))+2^{n-1} = 2^{n-1}(n-1)+2^{n-1} = 2^{n-1}n$$ Our guess was indeed correct and we have found a formula for $a_n$.