0 Daumen
727 Aufrufe

Hallo, ich bräuchte bitte eure Hilfe ich habe eine Frage zu den folgenden Aufgaben.


Aufgabe:

Lösen Sie mittels vollständiger Induktion. Sei jeweils n∈ℕ
(i) 5|(11n-6)
(ii) Sei A eine beliebige Menge mit |A| = n,n ∈ ℕ ∪ {0} . Ist P(A) die Potenzmenge von A, so gilt |P(A)| = 2n.


Problem/Ansatz:
Lösungsvoschlag Aufgabe 1:
Ich habe die erste Aufgabe so bearbeitet, ich denke das würde so passen oder:

Induktionsanfang:
n = 1
111-6 = 5
5|5 w.A.

Induktionsbehauptung: Angenommen 5|(11n-6) gelte für festes aber beliebiges n∈ℕ.

Induktionsschluss: (n+1), teilt die Zahl auch 5|(11n+1-6)
11n+1-6 = 11*11n-6 = (11n-6)+10*11n

(11n-6) ... Induktionsvoraussetzung
10*11n ... durch 5 teilbar
q.e.d.
                               

Wie gehe ich nun jedoch bei der Aufgabe 2 vor, wie mache ich hier die Induktion, weiß das jemand? Und passt meine erste Induktion? Danke vielmals und falls was nicht lesbar ist, bitte melden, ist nämlich mein erster Beitrag hier!      

Avatar von

1 Antwort

0 Daumen

(i) Ist denke ich okay.

(ii) Induktionsanfang für die leere Menge ist denke ich klar (\(P(\varnothing)=\{\varnothing\}\)).

Induktionshypothese: Für eine Menge \(A'=\{a_1,...,a_n\}\) und festem \(n\in \mathbb{N}\) gelte \(|P(A')|=2^n\).

In den Induktionsschritten nimmst du wg. der Endlichkeit an, du hättest eine Menge \(A\) mit \(A=\{a_1,...,a_{n+1}\}\).

Für die Menge \(A'=\{a_1,...,a_n\}\) weißt du nach Induktionsannahme, dass \(|P(A')|=2^n\).

Nutze dann \(P(A)=\{X| \ X\subseteq A'\} \cup \{X\cup \{a_{n+1}\}| \ X\subseteq A'\}\) und folgere aus der Disjunktheit der beiden Mengen in Verbindung mit der Induktionshypothese den Rest.

Avatar von 2,9 k

Ich war heute in meiner Lieblingspizzeria bei Alfredo und ich werde jetzt mal versuchen dir zu erklären, wieso mich seine Speisekarte an deine Aufgabe erinnert.

Alle seine Pizzen werden zunächst mit Tomaten und Käse belegt, das ist nichts besonderes. Dann hat Alfredo in seiner Küche eine Zutatenliste, aus der er gewisse Extrabeläge auswählen kann, um sie auf seine Pizzen zu legen. Je nach Auswahl erfindet er klangvolle Namen für seine Kreationen und schreibt die in seine Speisekarte für die Gäste.

Hier ist ein Ausschnitt aus seiner Speisekarte :

Pizza Margerita : mit Tomaten und Käse und sonst nichts
Pizza Funghi : mit Tomaten, Käse und Pilzen
Pizza Salami : mit Tomaten, Käse und Salami
Pizza PrimaDonna : mit Tomaten, Käse und Pilzen und Schinken
Pizza DonAlfredo : mit Tomaten, Käse und Salami und Schinken und Gurke
...

(das und sonst nichts habe ich eingefügt)


Der Zusammenhang mit deiner Aufgabe ist nun folgender :

Die Zutatenliste entspricht der Menge M, die komplette Speisekarte entspricht der Potenzmenge P(M)  (was "komplett" bedeuten soll erkläre ich gleich). Jede Pizza auf der Speisekarte entspricht einer bestimmten Auswahl an Extrabelägen, d.h. einer Teilmenge von M. Wenn man alle möglichen Teilmengen von M betrachtet, erhält man die "Menge aller Teilmengen", das ist die Potenzmenge von M. Dem entsprechen alle möglichen Kombinationen von Extrabelägen, also alle möglichen Pizzen, eben die in diesem Sinne komplette Speisekarte.

Die Anzahl möglicher Extrabeläge (also wie viele Zutaten Alfredo zur Verfügung stehen) ist die Anzahl der Elemente von M (man nennt das auch die "Mächtigkeit" von M) und dafür wird |M| geschrieben.
Die Aufgabe besteht nun darin, zu untersuchen, wie viele Pizzen auf einer kompletten Speisekarte stehen, wenn Alfredo 5 (oder 7 oder 0 oder allgemein |M|) Zutaten zur Auswahl hat, d.h. gesucht ist die Mächtigkeit der Potenzmenge, also |P(M)|.


Machen wir ein paar Beispiele :

Wenn Alfredo gar keinen Extrabelag mehr hat (d.h. M = ∅ , |M| = 0), so kann er doch immerhin noch Pizza Margerita anbieten (allerdings auch keine andere), die komplette Speisekarte hat einen Eintrag, |P(M)| = 1. Mathematiker schreiben dafür P(∅)   = {∅ }

Wenn Alfredo Artischocken hat (M = {a}), stehen auf seiner Speisekarte zwei Pizzen, nämlich Pizza Margerita und Pizza Pompeji (die mit Artischocken) : P(M) = {Margerita, Pompeji} = { ∅ , {a} }

Wenn Alfredo zwei Zutaten hat, Artischocken und Bananen ( M = {a , b} ), dann kann er jetzt schon vier Pizzen anbieten, nämlich Margerita, Pompeji, Vesuvo (die mit Banane) und Cäsar (die mit Artischocken und Banane)  P(M) = {Margerita, Pompeji, Vesuvo, Cäsar} = { ∅ , {a} , {b} , {a,b} }

So hatte also Alfredo seine Zutatenliste, seine Gäste hatten die Speisekarte, alle waren glücklich und zufrieden. Da tauchte eines Tages ein Fremder auf, der eine exotische Zutat mitbrachte, von der keiner je zuvor etwas gehört hatte : Eisbein. Er verlangete, dass Eisbein auf die Zutatenliste gesetzt wird. Dadurch wurde |Malt| → |Mneu| = |Malt| + 1 . Wie veränderte sich der Umfang der Speisekarte also |P(M)| ? Die alten Pizzen konnten natürlich bleiben, aber zusätzlich konnten diese außerdem auch noch mit Eisbein belegt werden, es gab also jetzt doppelt so viele Pizzen wie vorher :  |P(Malt)| → |P(Mneu)| = 2*|P(Malt)| . Jede neue Zutat verdoppelt den Umfang der Speisekarte, wenn M ein Element mehr erhält, verdoppelt sich die Mächtigkeit seiner Potenzmenge.

Mächtigkeit von M
0
1
2
3
4
5
...
n
Mächtigkeit von P(M)
1
2
4
8
16
32
...
2^n


Das ist im Prizip der Induktionsbeweis dafür, dass |P(M)| = 2|M|   ist.


Zusatz für Zweitsemester : Eines Tages kam der Teufel in die Pizzeria und verlangte, dass auch Pizzen als Belag auf Pizzen zugelassen sein sollten.
Pizza Diavolo sollte die Pizza Diavolo als Belag enthalten ...

Da wandte sich Alfredo an seinen Freund Bertrand um Rat. Bertrand schlug ihm vor, doch zunächst mal nur solche Pizzen anzubieten, die sich selbst nicht als Belag enthalten, solche Pizzen seien doch harmlos . Als Belohnung für seinen Ratschlag sagte Bertrand : "Dafür machst du mir jetzt bitte eine "Pizza Ultima", das ist die Pizza, die alle harmlosen Pizzen als Belag enthält." Alfredo hat Bertrand nie wieder seinen Freund genannt.

Wow, ich habe dein Kommentar erst jetzt gesehen. Ich weiß gar nicht was ich dazu sagen soll, ich möchte dir einmal meinen Dank aussprechen, denn die Mühe die du dir hier gemacht hast, ist einmalig. Hierzu muss man sich wirklich bedanken!

Das ist wirklich verständlich erklärt und sich das mit einen so guten Beispiel. Ich denke so bleibt das auch in Erinnerung, und das ist wichtig, das man dadurch dann weiß wie man es anzuwenden hat.

Ich schaue mir das morgen dann nochmals in aller Ruhe an, aber wenn ich jetzt zu später Stunde das ganze schon so ziemlich verstehe, dann beweist dies, das es einfach gut erklärt ist.

Nochmals danke, für die ganze Arbeit hier mir das so zu erklären, ich hoffe auch das dieses Kommentar für andere nützlich ist.

Beste Grüße

Max

P.S. Vielleicht postest du dein Kommentar noch als eigenständige Antwort, dann kann ich, falls da doch noch eine Frage aufkommt dazu kommentieren und dann ist es auch für andere leichter nachverfolgbar.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community