${\displaystyle {}P(axxax)=axaxxaxaxax\,.}$

${\displaystyle {}w_{n}=P^{n}(x)\,,}$

insbesondere ist ${\displaystyle {}w_{0}=x}$. Wir behaupten, dass in ${\displaystyle {}w_{n}}$ die Anzahl der ${\displaystyle {}x}$ gleich ${\displaystyle {}2^{n}}$ und die Anzahl der ${\displaystyle {}a}$ gleich ${\displaystyle {}2^{n}-1}$ und somit die Anzahl der Buchstaben gleich ${\displaystyle {}2^{n+1}-1}$ ist. Diese Aussagen beweisen wir durch Induktion über ${\displaystyle {}n}$. Für ${\displaystyle {}n=0}$ sind sie richtig. Seien sie nun für ${\displaystyle {}n}$ bewiesen, wir wissen also, dass es in ${\displaystyle {}w_{n}}$ genau ${\displaystyle {}2^{n}}$ viele ${\displaystyle {}x}$ und ${\displaystyle {}2^{n}-1}$ viele ${\displaystyle {}a}$ gibt. Beim Ersetzungsprozess bleiben die ${\displaystyle {}a}$ stehen, und die ${\displaystyle {}x}$ werden durch ${\displaystyle {}xax}$ ersetzt. Daher ist die Anzahl der ${\displaystyle {}x}$ in ${\displaystyle {}w_{n+1}}$ gleich

${\displaystyle {}2^{n}\cdot 2=2^{n+1}\,}$

und die Anzahl der ${\displaystyle {}a}$ in ${\displaystyle {}w_{n+1}}$ gleich

${\displaystyle {}2^{n}-1+2^{n}=2^{n+1}-1\,.}$