Is there a mathematical proof that n-dimensional cube has $2^n$ vertices? I have read that an n-dimensional cube has $2^n$ vertices, but I can't find a proof for that. What is the explanation to why that's true?
 A: You can define an interval, a square, a cube, a tesseract, an hypercube… by its vertices
$$(0),(1)$$
$$(0,0), (0,1), (1,0), (1,1)$$
$$(0,0,0), (0,1,0), (0,0,1), (0,1,1), (1,0, 0), (1,1,0), (1,0,1), (1,1,1)$$
$$(0,0,0,0), (0,0,1,0), (0,0,0,1), (0,0,1,1), (0,1,0, 0), (0,1,1,0), (0,1,0,1), (0,1,1,1), (1,0,0,0), (1,0,1,0), (1,0,0,1), (1,0,1,1), (1,1,0, 0), (1,1,1,0), (1,1,0,1), (1,1,1,1)$$
$$\cdots$$
In $n$ dimensions, $2^n$ points (number of arrangements with replacement).
A: This is best proved by induction. Let $\gamma_n$ denote the general hypercube. The hypercube $\gamma_{n+1}$ is $\gamma_n \times \gamma_1$, where $\gamma_1$ is the line segment. So, if $\gamma_n$ has $n_k$ components of the form $\gamma_k$, then $\gamma_{n+1}$ has $2n_k+n_{k-1}$ components of the form $\gamma_k$. That is, for each $\gamma_k$ in $\gamma_n$, we have $\gamma_k×\lbrace0\rbrace$ and $\gamma_k×\lbrace1\rbrace$ in $\gamma_{n+1}$ (one $\gamma_k$ in the "bottom" of the hypercube $\gamma_{n+1}$ and one in the "top," or $2n_k$ total), and, for each $\gamma_{k-1}$ in $\gamma_n$, we have $\gamma_{k-1}\times\gamma_1$ in $\gamma_{n+1}$ (contained in the "lateral" elements $\gamma_{n+1}$, for $n_{k-1}$ total).
For example, as we go from the square to the cube, the single face of the square gives rise to two faces in the cube (the "bottom" and the "top") and each edge in the square gives rise to one face in the cube (a lateral face connecting two corresponding edges in the "bottom" and the "top"). So there are $2\cdot1+4 = 6$ faces total in the cube.
This is the inductive step in the proof that the number of $\gamma_k$ components in $\gamma_n$ is $n_k=2^{n-k} {{n}\choose{k}}$. The formula for vertices is a special case: $n_0=2^n$.
This is all proved more simply if all we care about is vertices: if $\gamma_n$ has $2^n$ vertices, then $\gamma_{n+1} = \gamma_n \times \gamma_1$ has $2\cdot 2^{n}=2^{n+1}$ vertices.
