Wörter/Einsetzung/Anzahl/1/Aufgabe/Lösung

1. Es ist

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

2. Es sei

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

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

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

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

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

Zur gelösten Aufgabe