Fakultät als Summe darstellen < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:32 Mo 03.02.2014 | | Autor: | gladixy |
| Aufgabe | | Sei n eine natürliche Zahl. Für jede Teilmenge A, welche eine Untermenge von {1, ...., n} ist, die keine zwei aufeinanderfolgenden Zahlen enthält, sei [mm] p_A [/mm] das Produkt der Elemente von A. Wir legen noch fest, dass p_leere-Menge = 1 ist. Zeigen Sie, dass die Summe über alle [mm] (p_A)^2 [/mm] gleich (n+1)! ist. |
Hallo Vorhilfe-Community,
Vorweg: Ich bin mir nicht zu 100% sicher, ob ich diese Diskussion in die richtige Kategorie eingeordnet habe.
Ich habe zwar die komplette Aufgabenstellung hingeschrieben, aber letztendlich wäre mir sehr geholfen, wenn mir jemand einen Tipp geben könnte, ob die rechte Seite der folgenden Gleichungen irgendeinem bekannten Schema entspricht:
3! = [mm] 1^2 [/mm] + [mm] 1^2 [/mm] + [mm] 2^2
[/mm]
4! = [mm] 1^2 [/mm] + [mm] 1^2 [/mm] + [mm] 2^2 [/mm] + [mm] 3^2 [/mm] + [mm] 3^2
[/mm]
5! = [mm] 1^2 [/mm] + [mm] 1^2 [/mm] + [mm] 2^2 [/mm] + [mm] 3^2 [/mm] + [mm] 3^2 [/mm] + [mm] 4^2 [/mm] + [mm] 4^2 [/mm] + [mm] 8^2
[/mm]
Ist das irgendein bekanntes Muster? Ich konnte leider keinen logischen Zusammenhang zwischen den beiden Seiten der Gleichungen feststellen. (Ausser, dass sie natürlich das selbe Ergebnis liefern).
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Mit freundlichen Grüssen
glad
|
|
| |
|
Hallo glad,
schicke Aufgabe. Da muss man erstmal drauf kommen.
> Sei n eine natürliche Zahl. Für jede Teilmenge A, welche
> eine Untermenge von {1, ...., n} ist, die keine zwei
> aufeinanderfolgenden Zahlen enthält, sei [mm]p_A[/mm] das Produkt
> der Elemente von A. Wir legen noch fest, dass p_leere-Menge
> = 1 ist. Zeigen Sie, dass die Summe über alle [mm](p_A)^2[/mm]
> gleich (n+1)! ist.
>
>
> Hallo Vorhilfe-Community,
>
> Vorweg: Ich bin mir nicht zu 100% sicher, ob ich diese
> Diskussion in die richtige Kategorie eingeordnet habe.
Ich auch nicht, aber im Moment hätte ich da keinen Verbesserungsvorschlag. Vielleicht sehen wir den, wenn die Lösung vorliegt.
> Ich habe zwar die komplette Aufgabenstellung
> hingeschrieben, aber letztendlich wäre mir sehr geholfen,
> wenn mir jemand einen Tipp geben könnte, ob die rechte
> Seite der folgenden Gleichungen irgendeinem bekannten
> Schema entspricht:
>
> 3! = [mm]1^2[/mm] + [mm]1^2[/mm] + [mm]2^2[/mm]
> 4! = [mm]1^2[/mm] + [mm]1^2[/mm] + [mm]2^2[/mm] + [mm]3^2[/mm] + [mm]3^2[/mm]
> 5! = [mm]1^2[/mm] + [mm]1^2[/mm] + [mm]2^2[/mm] + [mm]3^2[/mm] + [mm]3^2[/mm] + [mm]4^2[/mm] + [mm]4^2[/mm] + [mm]8^2[/mm]
>
> Ist das irgendein bekanntes Muster?
Nicht dass ich wüsste...
> Ich konnte leider
> keinen logischen Zusammenhang zwischen den beiden Seiten
> der Gleichungen feststellen. (Ausser, dass sie natürlich
> das selbe Ergebnis liefern).
Ich würde hier ganz eindeutig vollständige Induktion empfehlen. Da muss man ja "nur" zwischen Teilmengen vom Typ [mm] n\in{A} [/mm] und [mm] n\not\in{A} [/mm] unterscheiden. 
Trotzdem ist das nicht so einfach, wie es anfangs aussieht; klappt aber.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:08 Mo 03.02.2014 | | Autor: | gladixy |
Danke für deine Antwort.
Leider kriege ich keine vollständige Induktion hin für das Problem. Ich scheitere am Induktionsschritt.
Was ich habe ist nicht viel:
Bezeichne [mm] T_n [/mm] die Lösung für ein beliebiges n [mm] \in \IN [/mm] und [mm] M_n [/mm] die Menge aller Elemente aus A, welche für die Berechnung von [mm] T_n [/mm] zulässig sind.
Induktionsvoraussetzung: Es gilt (n + 1)! für ein beliebiges n [mm] \in \IN. [/mm] Dann muss für [mm] T_n_+_1 [/mm] als Zwischenergebnis gelten:
[mm] T_n_+_1 [/mm] = (n + 1)!
Dem ist so, da alle Elemente aus [mm] M_n [/mm] in [mm] M_n_+_1 [/mm] immer noch gültig sind.
Wenn man die Aufgabe für ein paar n manuell durchgeht sieht man, dass [mm] T_n [/mm] * (n + 1) = [mm] T_n_+_1 [/mm]
Ausserdem gilt, dass alle Elemente, die in [mm] M_n_+_1 [/mm] hinzukommen in der Berechnung von [mm] T_n_+_1 [/mm] insgesamt n * [mm] T_n [/mm] zum Ergebnis [mm] (T_n_+_1) [/mm] beitragen.
Aber ich finde einfach keine logische und vor allen Dingen saubere Erklärung dafür...
Kann mir vielleicht jemand dahingehend ein Tipp geben?
Mit freundlichen Grüssen
glad
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:54 Mo 03.02.2014 | | Autor: | Sax |
Hi,
Reverend hat ja den entscheidenden Tipp gegeben.
Wenn die Behaupting für die Menge [mm] X_n=\{1, 2, ..., n\} [/mm] gezeigt ist, und wir jetzt noch das Element n+1 hinzunehmen, dann bleiben natürlich alle alten zulässigen Teilmengen erhalten, und es kommen neue hinzu, die das Element n+1 enthalten. Diese neuen können aber das Element n nicht enthalten (keine zwei aufeinander folgenden). Das Element n+1 kann also gerade zu jeder zulässigen Teilmenge von [mm] X_{n-1} [/mm] hinzugefügt werden, die entsprechenden Produkte werden also alle um den Faktor n+1 vergrößert, ihre Quadrate um den Faktor [mm] (n+1)^2. [/mm]
Somit ergibt sich für die neue Summe der Quadratzahlen $ (n+1)! + [mm] (n+1)^2*n! [/mm] = (n+1)!*(1+(n+1))=(n+2)! $
Gruß Sax.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:51 Mo 03.02.2014 | | Autor: | gladixy |
Okay. Ich glaube ich verstehe es jetzt einigermassen. Eine Sache ist mir noch unklar:
Wenn ich es richtig sehe, benutzt du eine Induktionsvoraussetzung, welche sagt, dass (n + 1)! für zwei aufeinanderfolgende n gilt , da man sonst nicht sagen kann, was das Ergebnis von [mm] X_n_-_1 [/mm] (nämlich n!) ist.
Wenn das stimmen sollte frage ich mich, ob das grundsätzich erlaubt ist. Ich dachte nämlich, dass man für den Induktionsschritt als Voraussetzung nur annehmen darf, dass (n + 1)! bzw. worum auch immer es in der Aufgabe geht für ein einziges bestimmtes n gilt.
Ausserdem würde mich interessieren, ob ich für diesen Beweis im Induktionsanfang zwei aufeinanderfolgende Glieder berechnen müsste.
Mit freundlichen Grüssen
glad
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:56 Mo 03.02.2014 | | Autor: | Sax |
Hi,
du hast grundsätzlich Recht.
Der Induktionsanfang muss also hier darin bestehen, die Behauptung für die ersten beiden Werte von n "zu Fuß" nachzuweisen.
Gruß Sax.
|
|
|
|
