Induktionsbeweis

Aufrufe: 1056     Aktiv: 28.05.2020 um 22:08

0

Hallo ich müsste folgende Aufgabe lösen. 
1. Zeigen Sie die Formel für die Anzahl aller n-Tupel durch Induktion nach n. 
ich habe hier einen Lösungsansatz, weiss dass er nicht korrekt notiert ist, wäre aber froh wenn sich jemand mein Gedankengang anschauen könnte uns sagen könnte ob dieser wenigstens stimmt. 

danke für die Antwort  

 

Diese Frage melden
gefragt

Student, Punkte: 1.95K

 
Kommentar schreiben
1 Antwort
1

Der Beweis ist von der Idee her gut. Allerdings gibt es eine Lücke im Beweis. Du benutzt nämlich im Induktionsschritt (zweite Äquivalenz) die Aussage für n=2. Die musst du also im Induktionsanfang auch noch beweisen.

Außerdem solltest du wirklich versuchen, den Induktionsschritt nicht mit Äquivalenzumformungen zu machen. Das ist ganz schlechter Stil. Eine Gleichungskette ist viel eleganter.

Diese Antwort melden
geantwortet

Student, Punkte: 7.02K

 

sorry komme nicht ganz draus, wo habe ich die Aussage mit n=2 verwendet?   ─   karate 28.05.2020 um 21:35

Beim zweiten Äquivalenzzeichen hast du verwendet, dass man die Tupel auseinanderziehen darf. Das ist aber keine triviale Aussage, sondern etwas, das man beweisen muss.   ─   42 28.05.2020 um 21:38

aha okei hättest du also einen Vorschlag wie du das machen würdest?
  ─   karate 28.05.2020 um 21:45

Ich würde den Induktionsschritt so machen: Wir betrachte die Zerlegung \( \{ (x_1, \dots, x_n, x_{n+1}) \vert x_i \in M \} = \cup_{a \in M} \{ (x_1, \dots, x_n, a) \vert x_i \in M \} \). Dies ist offensichtlich eine Partition. Außerdem betrachten wir für alle \(a \in M\) die Abbildung \( f: \{ (x_1, \dots, x_n, a) \vert x_i \in M \} \rightarrow \{ (x_1, \dots, x_n) \vert x_i \in M \}, (x_1, \dots, x_n, a) \rightarrow (x_1, \dots, x_n) \). Dies ist eine Bijektion. Insgesamt gilt also \( \vert \{ (x_1, \dots, x_n, x_{n+1}) \vert x_i \in M \} \vert \) \(= \sum_{a \in M} \vert \{ (x_1, \dots, x_n, a) \vert x_i \in M \} \vert \) \(= \sum_{a \in M} \vert \{ (x_1, \dots, x_n) \vert x_i \in M \} \vert \) \(= \sum_{a \in M} k^n \) \(= k^n \sum_{a \in M} 1 \) \(= k^n \cdot \vert M \vert \) \(= k^n \cdot k = k^{n+1} \).   ─   42 28.05.2020 um 22:06

Kommentar schreiben