Proving the number of k-dimensional components for the cross polytope The following property is given for the cross-polytope in various places (e.g. in the Wikipedia article on the cross-polytope):
The number of k-dimensional components (vertices, edges, faces, etc) of the n-dimensional cross-polytope is:
$2^{k+1}{n \choose {k+1}}$
How can this be proved? This is homework, so I'd prefer hints to actual solutions.
What I have so far is: it's pretty obvious to me that the number of vertices is two times the dimension, since we start out with 2 points (-1 and 1) for one dimension, and add two more on the orthogonal dimension for each step up in dimensions. I can also see how there are 2^n different d-dimensional simplices contained in the cross-polytope: for each dimension (of which there are n), just choose either + or - its elementary vector and take the convex hull.
Finding intermediate components doesn't seem to be equivalent to finding all subset polytopes, though. For instance, the square (2-orthoplex) has vertices (-1 0), (1 0), (0 -1), (0 1). There are four edges (going along the edges). convex((-1 0) (1 0)) also fits inside the square, yet there's no edge between (-1 0) and (1 0).
 A: The $2^{k+1}$ suggests that you're answering $k + 1$ yes/no questions (or perhaps $+$/$-$ questions?).
The ${n \choose {k+1}}$ has a natural interpretation, but as you've rightly pointed out, it's not ${2n \choose k + 1}$. Why should we only be allowed to choose from half of the vertices available?
To answer that question, let's look more closely at your two-dimensional example. For the square, I'd like to call the vertices $\pm e_i$ for $i = 1, 2$. You noted that $e_1$ and $-e_1$ aren't endpoints of a single edge; geometrically, the line connecting these points goes through the origin, and we definitely don't want that for a face. Can we turn this into a criterion for determining which subsets are the vertex sets of faces?
A: The main idea is to prove by induction. For that to work, you have to get aware that the (n+1)D cross-polytope is nothing but a bipyramid with an nD cross-polytope for base.
First consider the vertices. Those are the nD ones plus one atop and one below. - The former ones have been (induction base with $k=0$)
$$2^{0+1}{{n-1} \choose {0+1}}=2(n-1)$$
The induction step here therefore is
$$2(n-1)+2=2n=2^{0+1}{n \choose {0+1}}$$
 
Next consider the (n-1)D facets themselves. Those can be given directly, one per vertex of the dual hypercube, i.e.
$$2^n=2^n{n \choose n}=2^{(n-1)+1}{n \choose {(n-1)+1}}$$
 
For the remainder you will have 2 origins for kD facets: Those which derive as pyramids from (k-1)D elements of the equatorial (n-1)D cross-polytope (their bases). The according count will be doubled, as the pyramids will point up resp. down. And furthermore there are the kD elements of the equatorial (n-1)D cross-polytope themselves. Therefore we get here by induction base
$$2\cdot 2^{(k-1)+1}{{n-1} \choose {(k-1)+1}}+2^{k+1}{{n-1} \choose {k+1}}=2^{k+1}({{n-1} \choose k}+{{n-1} \choose {k+1}})$$
The remainder then is just the addition rule within the Pascal's triangle
$${{n-1} \choose k}+{{n-1} \choose {k+1}}={n \choose {k+1}}$$
--- rk
