MATH.19:5.2 - Discover the lemma needed to repeat a composition

Let f and g be maps X->X with f composed with g equal to g composed with f. Write composition as juxtaposition, with fg meaning apply g first and then f. Define f^0=id and f^(n+1)=f^n f, and similarly for g. Prove:

(fg)^n=f^n g^n

for every natural n.

The base n=0 holds. At the next step, the proposed induction hypothesis gives:

(fg)^(n+1)=f^n g^n f g.

The target is f^(n+1)g^(n+1). The difference exposes a missing lemma: g^n f=f g^n. This states precisely how to move f past the repeated g.

Prove that lemma by induction. At n=0 both sides are f. If it holds at n, then:

g^(n+1)f=g^n g f=g^n f g=f g^n g=f g^(n+1).

The second equality uses gf=fg; the third uses the lemma’s induction hypothesis. Return to the original step:

f^n g^n f g=f^n f g^n g=f^(n+1)g^(n+1).

The two inductions now have separate proved responsibilities. MATH.4 supplies their general induction method; the present work found which additional statement makes the main step possible.

Remove the commutation premise. On integers, f(x)=x+1 and g(x)=2x give (fg)^2(0)=3, while f^2 g^2(0)=2. The theorem has become false. Retaining the premise or retaining the actual interleaved composition are different useful responses; continuing the old rearrangement would lose the result needed by the calculation.