Bewies einer Summe < Sonstiges < Lin. Algebra/Vektor < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:56 Mi 24.10.2007 | | Autor: | dentist |
| Aufgabe | | Beweisen Sie eine endliche Menge mit [mm] n\in [/mm] N hat [mm] 2^n [/mm] verschiedene Teilmengen. |
Unser Prof hat dann irgendwie an die Tafel geschrieben!
[mm] \summe_{k=1}^{n} [/mm] = [mm] 2^n
[/mm]
und das daruas eben folgert [mm] 2^n [/mm] + [mm] \vektor{n+1\\k} =2^{n+1}!
[/mm]
Letzteres ist irgendwie aus logischem verständnis klar! aber wie man das mit [mm] 2^n [/mm] kommen soll ist mir sowas von ein rätsel! Irgendwas mit vollständiger induktion aber selbst die hab ich nicht kapier! ich glaub ich bin im falschen Studiengang! :-( bitte um hilfe!
danke für eure mühe im vorraus! ich hoffe es kann mir jemand noch bis morgen früh helfen! morgen ist nämlich abgebe von den übungen!!
wör total nett...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:30 Mi 24.10.2007 | | Autor: | Master_G_A |
hi
schau dir doch eifach mal kleine Mengen an
Z.B. für n= 1, n= 2 und n=3
n = 1 => klar...
Elemente:1
Teilmengen:1?
n = 2
Elemente: 1, 2
Teilmengen: {1}, {2}, {1,2} ..... also 3?
n = 3
Elemente: 1, 2, 3
Teilmengen:{1},{2},{3},{1,2}{1,3}{2,3},{1,2,3}.... also 7?
fast.... denn zu jeder Menge gehört auch die leere Menge. 
Also...?
Gruß Guido
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:44 Mi 24.10.2007 | | Autor: | Sax |
Hi,
> Beweisen Sie eine endliche Menge mit [mm]n\in[/mm] N hat [mm]2^n[/mm]
> verschiedene Teilmengen.
> Unser Prof hat dann irgendwie an die Tafel geschrieben!
> [mm]\summe_{k=1}^{n}[/mm] = [mm]2^n[/mm]
Die Formel lautete vermutlich [mm]\summe_{k=0}^{n}\vektor{n \\ k}[/mm] = [mm]2^n[/mm]
Man erhält sie aus folgender Überlegung :
Der Binomialkoeffizient [mm] \vektor{n \\ k} [/mm] ist (per Definition) gleich der Anzahl der k-elementigen Teilmengen einer n-elementigen Menge. Wenn man nun die Anzahl aller Teilmengen wissen möchte, so muss man eben die Anzahl der 0-elementigen (1 leere Menge), die Anzahl der 1-elementigen (davon gibt es n Stück), die Anzahl der 2-elementigen, ... , die Anzahl der n-elementigen (die Menge selbst) Teilmengen addieren (linke Seite der Gleichung).
Andererseits gilt der Binomische Satz : (a + b [mm] )^n [/mm] = [mm]\summe_{k=0}^{n}\vektor{n \\ k}a^k*b^{n-k}[/mm] (eine Art verallgemeinerte binomische Formel). Wenn man hierin a = 1 und b = 1 setzt, ergibt sich die obige Gleichung.
Die Anzahl der Teilmengen einer n-elementigen Menge erhälst Du aber auch aus folgender Überlegung :
Mit jedem weiteren Element der Menge verdoppelt sich die Anzahl der Teilmengen.
Die Teilmengen der neuen Menge sind nämlich erstens alle Teilmengen der alten Menge und zusätzlich eben all diese Mengen mit zusätzlich dem weiteren Element. Da eine 0-elementige Menge 1 Teilmenge hat (die leere Menge hat sich selbst als einzige Teilmenge), hat somit eine 1-elementige Menge 2 Teilmengen, eine 2-elementige Menge 4 Teilmengen, eine 3-elementige Mnge 8 Teilmengen u.s.w. (vst. Induktion).
> und das daruas eben folgert [mm]2^n[/mm] + [mm]\vektor{n+1\\k} =2^{n+1}![/mm]
>
> Letzteres ist irgendwie aus logischem verständnis klar!
(Da bist Du mir im Vorteil)
> aber wie man das mit [mm]2^n[/mm] kommen soll ist mir sowas von ein
> rätsel! Irgendwas mit vollständiger induktion aber selbst
> die hab ich nicht kapier! ich glaub ich bin im falschen
> Studiengang! :-( bitte um hilfe!
>
|
|
|
|
