Man halte fest, dass
$$ x * y^{2^n} = \left( y^{2^n} \right)^2 * x = y^{2^{n+1}} * x$$
für beliebige x, y gilt.
Jetzt Induktion über n.
IA: n = 1 ist als Voraussetzung gegeben.
IS:
IV: Für ein n ≥ 1 sei \( x^n * y = y^{2^n} * x^n \) für alle x, y
IB: Dann gilt auch \( x^{n+1} * y = y^{2^{n+1}} * x^{n+1} \) für alle x, y
Beweis:
Seien x ,y beliebig, dann ist
$$ x^{n+1} * y = x*(x^n * y) \stackrel{IV}{=} x * (y^{2^n} * x^n ) = (x * y^{2^n}) * x^n = \dotsm $$
Umklammern kann man hier stets wegen der Assoziativität.