The "Wu formula" and Steenrod algebras The Wikipedia page on Stiefel-Whitney classes includes the following paragraph:

Over the Steenrod algebra, the Stiefel–Whitney classes of a smooth
  manifold (defined as the Stiefel–Whitney classes of its tangent
  bundle) are generated by those of the form $w_{2^i}$ . In particular, the
  Stiefel–Whitney classes satisfy the Wu formula, named for Wu
  Wenjun:
  $\text{Sq}^i(w_j)=\sum_{t=0}^i {j+t-i-1 \choose t} w_{i-t}w_{j+t}.$

This seems to suggest the first sentence follows from the second, but the reference provided (to May's A Concise Course in Algebraic Topology) doesn't mention this. Personally, I can't see the connection. Is there some well-known lemma I'm missing?
 A: I don't think it is really clear from that Wikipedia page, but it is a bit clearer in May's book. 
You need to consider the construction of the Stiefel-Whitney classes on page 197 of May's book. 
i.e. There is a map 
$$\omega^\ast:H^*(BO(n);\mathbb{Z}_2) \to H^*((\mathbb{R} P^\infty;\mathbb{Z}_2)^{\Sigma_n}$$
which is an isomorphism and we define the Stiefel-Whitney classes by letting $w_i$ be the unique element such that $\omega^*(w_i)=\sigma_i$, where $\sigma_i$ which is the $i$-th elementary symmetric polynomial (which makes sense since $H^*(BO(n);\mathbb{Z}_2)$ is a $\mathbb{Z}_2$-polynomial ring on the elementary symmetric polynomials), $w_0=1$ and $w_i=0$ for $i > n$. 
So we need to know what the Steenrod operations on $\mathbb{R} P^\infty$ are. Since this is a ring generated by a one-dimensional class, this is not too hard to do:
Claim: For $u \in H^1(\mathbb{R} P^\infty;\mathbb{Z}_2)$, $\text{Sq}^i(u^j) = \binom{j}{i}u^{j+1}$
Proof: The total Steenrod squaring operation is a ring homomorphism and $\text{Sq}(u) = \text{Sq}^0(u) + \text{Sq}^1(u) = u + u^2$, hence $\text{Sq}(u^j) = (u+u^2)^j$ and then you can get the result from the binomial formula. 
Then bump this up using the Cartan formula, and fingers crossed, you get something that looks like the Wikipedia page.
The other approach is to open up your (well worn, read, and studied) copy of Milnor-Staffesh. In Chapter 8 they give another definition of the Stiefel-Whitney classes. See page 91, where they use the Thom isomorphism to define the Stiefel-Whitney classes. 
Without explaining all the terms:


In other words $w_i(\xi)$ is the unique cohomology classes in $H^i(B;\mathbb{Z}_2)$ such that $\phi(w_i(\xi)) = \pi^*w_i(\xi) \smile u$ is equal to $\text{Sq}^i\phi(1) = \text{Sq}^i(u)$. 


(If you want to read more consult Milnor-Stasheff or read Akhil Matthew's blog post).
Then problem 8.1 asks you to derive the exact formula given on the Wikipedia page (it should go something like - it is true for line bundles by the claim above. Then if it is true for $\xi$ it is true for $\xi \oplus L$ where $L$=line bundle. Then use the splitting principle)
A: By expanding out the Wu formula and moving some terms over to the other side, you find that
$$
{j - 1 \choose i} w_{i+j} = Sq^i(w_j) + \sum_{t = 0}^{i-1} {j+t-i-1 \choose t} w_{i-t}w_{j+t}.
$$
If the binomial coefficient on the left is nonzero, this allows you to write $w_{i+j}$ as a sum of terms generated by lower Stiefel-Whitney classes.  So for a fixed $n$, this becomes a question as to whether there exist $i$, $j$ such that $i+j = n$ and $j-1 \choose i$ is nonzero.
If $n$ is not a power of $2$, we can write it as $2^k + i$ where $2^k > i$.  Then $2^k - 1 \choose i$ is nonzero.  (By Lucas' theorem, the binomial coefficient nonzero if and only if, in binary, the nonzero digits of $i$ are also nonzero digits of $j-1$.  The number $2^k-1$ has all of its binary digits nonzero, and $i$ is less than or equal to it.)
If $i+j$ is a power of two, then $i + (j - 1)$ has no zeros in its binary expansion, which means that $i$ and $j-1$ can't share any nonzero binary digits; there can be no carries when adding $i$ and $(j-1)$ together.
