My question is about the graph consisting of all $2^n$ points of $\{0, 1\}^n$, with edges between points that differ by only one coordinate.
I'm wondering: how many edges are there for a given $n$?
If we let $e_n$ denote the number of edges for $\{0, 1\}^n$, it is clear that $e_1 = 1$, since the graph corresponding to $\{0, 1\}^1$ is just two points with a line in between them.
Similarly $e_2=4$, since the graph for $n=2$ has the point $(0, 0)$, which connects to $(0, 1)$, which connects to $(1, 1)$, which connects to $(1, 0)$, which connects back to $(0, 0)$.
Similarly, $e_3=12$, since the graph for $\{0, 1\}$ is basically just a cube with the edges corresponding to the edges of the cube.
My hunch is that $e_{k+1}=2e_k+2^k$. I thought of this because when we go from $n=1$ to $n=2$, we basically double the number of edges but also add edges for each of the vertices in the original graph (which for $n=1$ were two). To go from $n=2$ to $n=3$ we again first double the number of edges in $n=2$ (because we are basically translating the square in 3-space) but then add an edge for each of the four vertices in the $n=2$ case (because as we translate the square it essentially creates a new place for there to be an edge for each vertex in the original square).
Is this formula correct, and if so does anyone have a more rigorous way to prove it? Can we get a nice closed formula (i.e., one that is not recursive)?
Note that this question is essentially asking how many edges a $k$-dimensional cube or $k$-cell has.
Your argument is essentially correct and you have obtained a correct recursive formula. You could have alternately used the degree-sum formula to obtain the number of edges directly by noticing that each vertex of $n$-dimensional cube has degree $n$.