Need help understanding Knuth's proof that: The set of all pure words is well-ordered by the relation >
Now let $\alpha$ be a pure word with $n_j$ symbols of degree $d_j$. It is easy to prove inductively that:
$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$
i.e. $n_0 = 1 + n_2 + 2n_3 + ...$

I think there is a small mistake here, since $n_j$ should be considered as the number of symbols of degree $j$ and not of degree $d_j$ in $\alpha$.

$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$

In this formula, the left side can be interpreted as &quot;the total number of symbols&quot;, and the right side can be interpreted as &quot;the first operator symbol plus the total number of arguments&quot;. Intuitively, those quantities are indeed equals.
If we correct the mistake, then it is somewhat easy to prove by induction:

if $\alpha$ does not contain any operator of degree $\geq 1$, then we have $\alpha = f()$, where $f$ is an operator of degree $0$ (that could be considered as a constant). We have then $n_0 = 1$, and $n_i = 0$ for any $i \geq 1$. The property $n_0 = 1 + n_2 + 2n_3 + ...$ holds;

if $\alpha = f(\alpha_1, …, \alpha_d)$ where $f$ is an operator of degree $d \geq 1$ and the $\alpha_i$ are pure words that verify the property we want to prove, then we get:

$n_k(\alpha) = \sum\limits_{i=1}^d n_k(\alpha_i)$ if $k \neq d$;
$n_d(\alpha) = 1 + \sum\limits_{i=1}^d n_d(\alpha_i)$.

Therefore we get:
$\begin{array}{rcl}
 n_0(\alpha)&amp; = &amp;\sum\limits_{i=1}^d n_0(\alpha_i) \\ &amp; =&amp; \sum\limits_{i=1}^d\left(1+\sum\limits_{k=2}^{\infty}(k-1)n_k(\alpha_i)\right)\\ &amp; = &amp; d + \sum\limits_{k=2}^{\infty}(k-1)\sum\limits_{i=1}^dn_k(\alpha_i) \\ &amp; =  &amp;d + (d-1)(n_d(\alpha) - 1) + \sum\limits_{k = 2,k\neq d}^{\infty}(k-1)n_k(\alpha)\\ &amp; = &amp; 1 + \sum\limits_{k = 2}^{\infty}(k-1)n_k(\alpha)\end{array}$
And that proves the formula by structural induction on pure words. Please note that the previous sums can be interverted because the infinite sum is, in fact, finite (since $n_k(\alpha_i) = 0$ for $k$ big enough).


The fact that $n_j$ is the number of symbols of degree $j$ and not of degree $d_j$ is somewhat confirmed after the statement: &quot;since each nullary operator has positive    weight, we have $w \geq n_0$&quot;. Why? Because $\alpha$ contains $n_0$ occurrences of nullary operators, which are supposed to be of positive weights. The statement would make no sense if $n_0$ was the number of symbols of degree $d_j$ (since $w_j$ could be zero).