Finding a recurrence relation for $Q_{n}$

Question

Find a recurrence relation for $a_{n}$ where $a_{n}$ denotes the number of edges in the n-cube $Q_{n}$.

I believe I'm supposed to do this by constructing $Q_{n}$ recursively from two copies of $Q_{n-1}$, but I'm not really sure how exactly to do that numerically. I also know that the answer is $S_{n}=2S_{n-1}+2^{n-1}, n\ge2$, but I have no idea of how one would get there.

Any help is appreciated, thanks in advance

Answer 1

Well we might as well do this for unit cubes, so why note consider the cube to be convex hull of $$\{(x_1,...,x_n)|x_i=0,1\}.$$ Then the vertices of the cube are precisely the elements of $$\{(x_1,...,x_n)|x_i=0,1\}.$$ Edges would correspond to elements of $$\{(x_1,...,x_n)|x_i=0,1\}$$ that differ by exactly one coordinate. In this case the two $Q_{n-1}s$ could be (we don't have a unique choice) the convex hulls of $$\{(x_1,...,0)|x_i=0,1\},$$ and $$\{(x_1,...,1)|x_i=0,1\}.$$ We know that $$\text{convexhull(\{(x_1,...,0)|x_i=0,1\})}$$ and $$\text{convexhull(\{(x_1,...,1)|x_i=0,1\})}$$ each have $S_{n-1}$ elements, so we need only consider edges joining them. They are precisely the line segments with endpoints $$(x_1,...,x_{n-1},0)$$ and $$(x_1,...,x_{n-1},1)$$ of which there are $2^{n-1}.$ This gives us $S_n=2S_{n-1}+2^{n-1}.$

Answer 2

HINT only

One way to characterize $Q_n$ is to realize that the vertices are $n$-bit vectors, i.e. $\{0,1\}^n$. E.g. for $Q_3$ the vertices are $000, 001, 010, 011, 100, 101, 110, 111$. For $Q_3$ specifically you can actually visualize these are coordinates in an $(x,y,z)$ Cartesian coordinate system. Then two vertices are adjacent iff they differ by exactly $1$ bit. E.g. $000$ has edges to $001, 010, 100$.

This should give you the recurrence almost immediately.

Does this make sense? Or do you need more help?