Palindrom mittels Induktion beweisen

24.10.2010, 12:41	Kettcar	Auf diesen Beitrag antworten »
Palindrom mittels Induktion beweisen Meine Frage: Schönen Sonntag, ich möchte mittels Induktion Folgendes beweisen: Es sei E ein Alphabet und das Wort w ein Palindrom aus E* Zu beweisen (über die Länge des Wortes): 1. $\begin{eqnarray} \lambda \end{eqnarray}$ ist ein Palindrom 2. Ist a ein beliebiges Symbol in E, so ist a ein Palindrom. 3. Ist a ein beliebiges Symbol in E und w ein Palindrom, so ist awa ein Palindrom. 4.Ein Wort ist kein Palindrom, falls es sich nicht durch 1., 2. oder 3. konstruieren lässt. Meine Ideen: Meine Idee ist nun folgende: Induktionsanfang: $\begin{eqnarray} <br /> \|w\| = 0 \vee \|w\| = 1<br /> w = \lambda = w^{rev} \vee w = a = w^{rev}<br /> \end{eqnarray}$ Induktionsschritt: $\begin{eqnarray} <br /> \|w\| \geq 2<br /> w = a_{n}...a_{1} v a_{1}...a_{n} \end{eqnarray}$ mit v ist Palindrom zu zeigen: $\begin{eqnarray} <br /> a_{n+1} w a_{n+1} = a_{n+1}a_{n}...a_{1} v a_{1}...a_{n}a_{n+1}<br /> \end{eqnarray}$ durch Einsetzen des Induktionsschritt auf der linken Seite der Gleichung erhaelt man: $\begin{eqnarray} <br /> a_{n+1}a_{n}...a_{1} v a_{1}...a_{n}a_{n+1} = a_{n+1}a_{n}...a_{1} v a_{1}...a_{n}a_{n+1}<br /> \end{eqnarray}$ Somit ist gezeigt, dass durch Umklammern eines Palindroms mit einem beliebigen Zeichen aus E ebenfalls ein Palindrom entsteht. Bin ich damit auf dem richtigen Weg? Hab ich damit die Punkte 1-3 bewiesen oder bin ich komplett auf dem Holzweg? Vielen Dank schonmal für eure Anmerkungen und einen schönen Sonntag!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »