Question. Let $p$ be a prime. Let $q$ be a power of $p$. Let $P^0$, $P^1$, $P^2$, ... be elements of some associative $\mathbb F_q$-algebra $A$. (Here, $P^i$ does not mean $P$ to the $i$-th power; instead, $i$ is an upper index.) Asume that the power series $\sum\limits_{a,k} \left(tu\right)^a P^a P^k$ and $\sum\limits_{c,j} u^c t^{qj}P^cP^j$ are equal, where $t$ is the indeterminate of our power series and $u=\left(1-t\right)^{q-1}=1+t+t^2+...+t^{q-1}$. Prove that any nonnegative integers $a$ and $b$ such that $a < qb$ satisfy
$\displaystyle P^aP^b = \sum\limits_j \left(-1\right)^{a-qj} \binom{\left(b-j\right)\left(q-1\right)-1}{a-qj} P^{a+b-j}P^j$.
(If you don't use the same conventions about negative binomial coefficients as I do, think of this sum as going from $j=0$ to $j=\left\lfloor a/q\right\rfloor$.)
Motivation. This question is equivalent to deriving the Adem-Wu relations in the Steenrod algebra (without the Bockstein) from the Bullett-Macdonald formula. I am working in the invariant-theoretical setting, so I want a proof which does not refer to the topological interpretation of the Steenrod algebra (at least not unless it shows that this is equivalent to the invariant-theoretical one).
Larry Smith, An algebraic introduction to the Steenrod algebra, arXiv:0903.4997 gives a proof using complex integration, but (the indexing mistakes put aside) I do not really believe it. It seems to work over $\mathbb Z$ first (which allows for integration) and then project onto $\mathbb F_q$, which is okay, but I think the condition that $\sum\limits_{a,k} \left(tu\right)^a P^a P^k = \sum\limits_{b\geq j} u^{b-j}t^{qj}P^{b-j}P^j$ cannot be "lifted" to $\mathbb Z$ in a straightforward way, to begin with, which puts the whole complex-analysis approach under question. Probably it works with the right incantations being said, but I was not able to come up with these incantations (and way too confused in this topic). A pedestrian algebraic proof would be preferred.