Induktionsbeweis - knifflig! < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:25 Sa 03.11.2007 | | Autor: | Casy |
| Aufgabe | Zu zeigen per vollständiger Induktion:
Sei n eine natürliche Zahl. Man nehme alle nichtleere Teilmengen der Menge {1,2,...n} der natürlichen Zahlen von 1 bis n. Für jede dieser Teilmengen bilde man das Produkt aller Elemente und nehme den Kehrwert. Summiert man diese Kehrwerte auf, erhält man n!!
BSP: Für n=3 sind die nichtleeren Teilmengen {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}. Die Produkte sind 1, 2, 3, 2, 3, 6, 6. Kehrwerte: 1/1, 1/2, 1/3, 1/2, 1/3, 1/6, 1/6. Aufsummiert: 1/1 + 1/2 + 1/3 etc... =3! |
Hallo!
Ich habe das Problem, dass ich schon die Induktionsaussage nicht hinkrieg.
Also, die Menge der Teilmengen ist schonmal 2hochn-1, für n+1 dann 2*2hochn-1.
Aber wie kann ich die Rechenoperationen (Produkt, Kehrwert, Addition) in eine Aussage fassen???
Für Tipps bin ich sehr dankbar!!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:08 Sa 03.11.2007 | | Autor: | Blech |
> Zu zeigen per vollständiger Induktion:
>
> Sei n eine natürliche Zahl. Man nehme alle nichtleere
> Teilmengen der Menge {1,2,...n} der natürlichen Zahlen von
> 1 bis n. Für jede dieser Teilmengen bilde man das Produkt
> aller Elemente und nehme den Kehrwert. Summiert man diese
> Kehrwerte auf, erhält man n!!
Nein, man erhält n.
>
> BSP: Für n=3 sind die nichtleeren Teilmengen
> {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}. Die Produkte sind 1,
> 2, 3, 2, 3, 6, 6. Kehrwerte: 1/1, 1/2, 1/3, 1/2, 1/3, 1/6,
> 1/6. Aufsummiert: 1/1 + 1/2 + 1/3 etc... =3!
Nein, die Summe ist 3, nicht 6.
Wir sind hier nicht auf www.chatten-bis-zum-umfallen.de!!!!!!!!11
Könntest Du vielleicht Deinen enthusiastischen Satzzeichengebrauch etwas zurückfahren, ganz besonders, wenn er die eigentliche Bedeutung Deiner Aussage entstellt???lolololkthxbye XOXOXOX
> Hallo!
>
> Ich habe das Problem, dass ich schon die Induktionsaussage
> nicht hinkrieg.
Du brauchst gar keine Informationen über die Anzahl an Mengen, die Du kriegst, es reicht für [mm] $n\to [/mm] n+1$, [mm] $\mathcal{P}$ [/mm] aufzuteilen in die Mengen, die
n+1 enthalten (für n=2, n+1=3 wären das {{3},{1,3},{2,3},{1,2,3}}) und jene, die das nicht tun ({{1},{2},{1,2}}).
Was fällt Dir bei den beiden Mengen (von Mengen) auf? =)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:20 Sa 03.11.2007 | | Autor: | Casy |
ok... sorry wegen der "!", hab nicht über mathematische Konsequenzen nachgedacht.
Also, nach deiner Beispielaufteilung fällt mir auf, dass sich die beiden Mengen von Mengen ergänzen zu der Gesamtmenge der Teilmengen, ist ja logisch....ehrlich gesagt, weiß ich nicht, wie ich das statt mit Zahlen mit n und n+1 anstellen soll..
Quasi ((1), (2), (...), (n), (1,2), (1,n), (2,n), (1,...,n))...nee, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:34 Sa 03.11.2007 | | Autor: | Blech |
> Also, nach deiner Beispielaufteilung fällt mir auf, dass
> sich die beiden Mengen von Mengen ergänzen zu der
> Gesamtmenge der Teilmengen,
Wir haben's ja gerade aufgeteilt, also wird's schon unsere urspr Menge ergeben, wenn wir sie wieder zusammen setzen.
Achte mal auf Ähnlichkeiten zw. den beiden. Worin unterscheiden sie sich denn bis auf die 3?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:44 Sa 03.11.2007 | | Autor: | Casy |
OK, einen Unterschied sehe ich darin: In der Menge mit n kommen immer kleinere Teilmengen raus als in denen mit n+1, weil ja n+1 die höhere Zahl ist...
Nee, sorry, ich steh voll auf dem Schlauch!
Kannst du mir bitte noch etwas auf die Sprünge helfen?
ich seh gar nicht, was mir diese Mengen von Mengen sagen sollen!
Vielleicht: wenn du sagst, "bis auf die 3", dann sind die Mengen ja gleich, wenn man die 3 ignoriert, weil die 3 zu jeder bestehenden Teilmenge dazukommt. dh die Menge der Teilmengen mit n und die mit n+1 sind identisch, und in der mit n+1 kommen nochmal dieselben Teilmengen MIT 3 vor.
So vielleicht?
|
|
|
| |
|
Hallo casy,
Die Aussage gilt ja z.B. für [mm]n=2[/mm]:
{1},{2},{1,2}
Also:
[mm]1+\frac{1}{2}+\frac{1}{2}=2[/mm]
Erkenne nun die rekursive Struktur dieser Aussage und benutze diese Struktur für die vollständige Induktion, um die Induktionsaussage sinnvoll einsetzen zu können:
Denn es gilt für [mm]n=3[/mm]:
{1},{2},{1,2} und alle Mengen nochmal aber mit 3 vereinigt, dazu noch {3}:
{1},{2},{1,2}, {1,3},{2,3},{1,2,3}, {3}
und das ist dasselbe wie:
[mm]\{1\},\{2\},\{1,2\},\quad\{3\}\cup\{1\},\{3\}\cup\{2\},\{3\}\cup\{1,2\},\quad\{3\}[/mm]
Du rechnest also:
[mm]\underbrace{2}_{\texttt{siehe vorige Rechnung}} + \frac{1}{2+1}\cdot{}\underbrace{2}_{\texttt{siehe vorige Rechnung}} + \frac{1}{2+1}=2+1=3[/mm]
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 13:36 Sa 03.11.2007 | | Autor: | Casy |
Super Erklärung, das mit der Vereinigung!
aber ehrlich gesagt komm ich nicht ganz auf die Induktionsaussage:
allein die Produkte innerhalb der Teilmengen müssen ja dargestellt werden (weil sie ja im Nenner gebraucht werden), und die wären 1, ..., n, 1*n, 2*n, ..., (n-1)*n, etc.
wie macht man denn sowas?
Deshalb kann ich auch nicht ganz nachvollziehen, wie du deine letzte Zeile aufgestellt hast.
Gruß!
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 14:10 Sa 03.11.2007 | | Autor: | Casy |
gut, also Rekursivität von 1 + 1/2 + 1/2 = 2 beachten.
Bei n=3 gilt dann:
1 + 1/2 + 1/3 + 1/2 + 1/3 + 1/6 + 1/6 = 3.
Meinst du mit Rekursivität, dass dieselben Brüche jeweils mehrmals auftauchen?
Tut mir ja leid, dass ich so aufm Schlauch steh, aber ich komm nicht auf die Induktionsaussage!
also: n + 1/(n+1) * n + 1/(n+1) = n + 1 hast du gemacht für n=2. Richtig?
Wenn ich dann aber nicht n+1, sondern nur n nehme, ergibt das für mich:
n + 1/n * n + 1/n = n, und das geht nicht für n=1!
Was hab ich falsch verstanden??
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:22 Mo 05.11.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:22 Mo 05.11.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
