vollständige Induktion < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:44 Sa 27.01.2007 | | Autor: | rEgEn |
| Aufgabe | | Sei M eine endliche Menge mit n Elementen. Zeigen Sie unter Verwendnung vollständiger Induktion: Die Anzahl der Teilmente von M ist [mm] 2^n. [/mm] (Auch die leere Menge wird als Teilmenge aufgefasst) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
was muss ich in der Aufgabe konkret tun bzw zeigen?
Klar der Anfang mit n=1. Aber wie schreib ich das auf?
also
[mm] 2^1 [/mm] = ???
dann die weiteren schritte
2^(n+1) klar aber gleich was muss das sein?
Bin für Tipps dankbar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:05 Sa 27.01.2007 | | Autor: | Sigrid |
Hallo
> Sei M eine endliche Menge mit n Elementen. Zeigen Sie unter
> Verwendnung vollständiger Induktion: Die Anzahl der
> Teilmente von M ist [mm]2^n.[/mm] (Auch die leere Menge wird als
> Teilmenge aufgefasst)
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Hallo,
>
> was muss ich in der Aufgabe konkret tun bzw zeigen?
>
> Klar der Anfang mit n=1. Aber wie schreib ich das auf?
> also
> [mm]2^1[/mm] = ???
Du musst zeigen, dass eine Menge mit einem Element genau [mm] 2^1=2 [/mm] Teilmengen hat. Das eine Element kannst du a nennen. dann ist
$ [mm] M=\{a\} [/mm] $
Jetzt überlege dir, wie viele Teilmengen M beseitzt.
>
> dann die weiteren schritte
> 2^(n+1) klar aber gleich was muss das sein?
Hier setzt du voraus, dass eine Menge M mit n Elementen [mm] 2^n [/mm] Teilmengen hat und zeigst dass daraus folgt, dass eine Menge M mit n+1 Elementen [mm] 2^{n+1} [/mm] Teilmengen hat.
Das kannst du folgendermaßen zeigen:
Du nimmst aus der Menge M ein Element (ich nenne es a) heraus. Die Restmenge (ich nenne sie M') hat dann n Elemente.
Damit weißt du nach Induktionsvoraussetzung, dass M' [mm] 2^n [/mm] Teilmengen hat.
Du musst jetzt zeigen, dass damit die Menge
$ M = M' [mm] \cup \{a\} [/mm] $
$ [mm] 2^n [/mm] + [mm] 2^n [/mm] = [mm] 2^{n+1} [/mm] $
Teilmengen hat.
Versuch's mal
Gruß
Sigrid
>
> Bin für Tipps dankbar.
|
|
|
|
