vollständige Induktion < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:32 Di 20.10.2009 | | Autor: | Serafyna |
Hallo zusammen,
ich sitz vor meinem Übungsblatt und habe folgendes Problem und bin dabei am Verzweifeln. Wäre echt super, wenn ihr mir helfen könnt.
| Aufgabe | Es sei M eine endliche Menge mit card M = n, und sei P(M) die Potenzmenge von M. Zeigen Sie: card P(M) = [mm] 2^n.
[/mm]
Hinweis: Machen Sie vollständige Induktion nach n. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
card M = n
card P(M) = [mm] 2^n
[/mm]
IA: n=1 card M = 1
=> P(M) = [mm] {\emptyset, 1}
[/mm]
=> card P(M) = 2 = [mm] 2^1 [/mm] = [mm] 2^n
[/mm]
IH: [mm] \summe_{k=1}^{n} [/mm] card P(M) = [mm] 2^n [/mm] für ein n Element N.
IS: n-> n+1
[mm] \summe_{k=1}^{n+1} [/mm] card P(M) = 2^(n+1)
= [mm] \summe_{k=1}^{n} n^2 [/mm] + 2^(n+1)
Vielen lieben Dank,
eure Silke
|
|
| |
|
Hallo Silke und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") ,
zunächst mal solltest du (noch)mal einen Blick auf die Forenregeln werfen, v.a. auf den Punkt "höflicher Umgangston"
Es ist doch kaum zuviel verlangt, mit einem knappen "Hallo" zu beginnen und "LG" am Ende zu schreiben, schließlich erwartest du immerhin kostenlose Hilfe
> Es sei M eine endliche Menge mit card M = n, und sei P(M)
> die Potenzmenge von M. Zeigen Sie: card P(M) = [mm]2^n.[/mm]
> Hinweis: Machen Sie vollständige Induktion nach n.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
>
> card M = n
> card P(M) = [mm]2^n[/mm]
>
> IA: n=1 card M = 1
> => P(M) = [mm]\{\emptyset, 1\}[/mm]
Ja, das stimmt im Prinzip, wenn auch das Element von $M$ nicht unbedingt 1 sein muss und du es lediglich als "Platzhalter" für das Element benutzt.
Genauer vllt.: Sei $M$ eine Menge mit $card(M)=1$, etwa [mm] $M=\{a\}$. [/mm] Dann ist [mm] $\mathcal{P}(M)=\{\emptyset,a\}$, [/mm] also [mm] $card(\mathcal{P}(M))=2=2^1$ [/mm] ...
>
> => card P(M) = 2 = [mm]2^1[/mm] = [mm]2^n[/mm]
>
> IH: [mm]\summe_{k=1}^{n}[/mm] card P(M) = [mm]2^n[/mm] für ein n Element N.
Huch?
Wie kommst du auf das Summenzeichen?
Die Induktionsvoraussetzung sollte lauten:
Sei [mm] $n\in\IN$ [/mm] beliebig, aber fest und sei $M$ eine Menge mit $card(M)=n$ und gelte [mm] $card(\mathcal{P}(M))=2^n$
[/mm]
>
> IS: n-> n+1
>
> [mm]\summe_{k=1}^{n+1}[/mm] card P(M) = 2^(n+1)
Nein, zu zeigen ist im Induktionsschritt, dass unter der Induktionsvoraussetzung für eine Menge $M'$ mit $n+1$ Elementen, also $card(M')=n+1$ gefälligst die Potenzmenge [mm] $\mathcal{P}(M')$ [/mm] auch [mm] $2^{n+1}$ [/mm] Elemente hat.
Dazu kannst du mal o.B.d.A. annehmen, dass [mm] $M'=M\cup \{x\}$ [/mm] mit [mm] $x\notin [/mm] M$ ist und die Teilmengen von $M'$ betrachten, die $x$ enthalten und jene, die $x$ nicht enthalten ...
>
> = [mm]\summe_{k=1}^{n} n^2[/mm] + 2^(n+1)
So ohne Kommentar zur Rechnung und v.a zum Auftauchen des Summenzeichen kann man schwerlich was genaueres sagen ...
Gruß
schachuzipus
|
|
|
|
