FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Mathematik

Wie löse ich diese Aufgabe? Induktion!

Wie löse ich diese Aufgabe? Induktion! 2008-03-19 02:05
Alexander_W
In der Klausur war eine Induktionsaufgabe, die folgend aussah.

und ich kann mir die Lösung überhaupt nicht erklären. hoffe es kann jemand helfen
Anhänge 1.jpg

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 08:53
UncleOwen
Hmm… einmal Symmetrie und einmal Additionstheorem, würd ich sagen.

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 08:53
Slater
schau dir doch mal die Definition von n über k an,
schreibe beide Terme als n!/ k! * (n-k)! oder wie das geht, dann siehst du das beides das gleiche ist

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 08:59
UncleOwen
schau dir doch mal die Definition von n über k an,
schreibe beide Terme als n!/ k! * (n-k)! oder wie das geht, dann siehst du das beides das gleiche ist

Holzhammer geht natürlich auch :)

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 13:38
Alexander_W
ich habe es bereits auf diese Weise versucht. Ich komme nie auf das gleiche, vielleicht, weil ich beim Rechnen mit den Fakultäten und so meine Probleme habe.

Würde sich einer die Mühe machen und mir das komplett vorrechnen? egal wem ich frage, niemand weiß warum das gleich ist. In der Klausur hatte es gereicht zu schreiben, dass laut Script und irgendwas mit Binoblablabla das gleich ist. ich will wissen warum das gleich ist.

würde mich freuen.

einmal Symmetrie und einmal Additionstheorem, Holzhammer … worüber redet ihr ? ;) schwer für uns Nichtmathematiker, euch zu folgen ;)

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 14:13
Fred
Holzhammer … worüber redet ihr ? ;)
Holzhammer bedeutet folgendes:

Um zu zeigen, dass A = B gilt, rechnest Du A und B so weit es geht aus. Wenn dann am Ende auf beiden Seiten der Gleichung derselbe Term steht, hast Du die Gleichheit gezeigt.

Wenn Du zum Beispiel zeigen willst, dass x+x+x = 4x-x gilt, reduzierst du die linke Seite auf 3x und die rechte Seite auf 3x und hast gewonnen.

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 14:32
Slater
> vorrechnen

mit Verlaub, das ist ja erbärmlich, Schul-Mathematik

ich gebe als Tipp eine Teilrechnung:
n+2 über n-1 = (n+2)!/ (n-1)! * 3! = (n+2) * (n+1) * n / 6

so in der Art rechnet man das auf beiden Seiten hin und her, kürzt, erweitert, verwendet Schul-Mathematik-Binomische Formeln usw.

rechne mal selber etwas und poste wenigstens eine anständige Frage zu einen bestimmten Rechnenschritt,
dann kann man da evtl. helfen

>  ich will wissen warum das gleich ist.

warum willst du das überhaupt wissen, wenn du es nicht selber rechnen kannst? ;)
es wäre besser, wenn du erstmal wissen möchten würdest, was Fakultät, Bruchrechung und Binomische Formeln sind

(ich glaube das klingt jetzt alles sehr hart, den Ton habe ich mir vom Java-Anfänger-Forum angewöhnt, nicht persönlich nehmen ;) )

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 14:36
Fred
Ach DU bist SlaterB? Ich bin JavaFred [28]

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 14:41
Slater
also deinen Namen gibts ja häufiger, aber ich bin doch wohl unverkennbar ;)
habs nach Jahren sogar geschafft, den Smily einzublenden

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-19 17:04
Loom
1. Aufgabe ist laut GProt im Wiki anders, dann stimmt es aber auch für n=2 ;)

2. Hab ja grad nix besseres zu tun:

[latex]\sum^n_{k=2}{k \choose 2} + {n+1 \choose 2} = {n+1 \choose n-2} + {n+1 \choose 2}[/latex]

i. Holzhammer: =[latex]\frac{(n+1)(n)(n-1)\dots(n-(n-2)+1)}{(n-2)(n-3)(n-4)\dots\cdot 2 \cdot 1}[/latex] + [latex]\frac{(n+1)(n)(n-1)\dots(n-(n-2)+1)}{2 \cdot 1}[/latex]
=[latex]\frac{(n+1)(n)(n-1)}{2 \cdot 1}[/latex] + [latex]\frac{(n+1)(n)(n-1)\dots\cdot 3}{2 \cdot 1}[/latex] Fortsetzung folgt (hab doch was besseres zu tun :P

ii. Satz im Skript (keine Ahnung wo, S. 47?): [latex]{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}[/latex]

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-21 16:56
Alexander_W
was meinst du mit anders? für mich sind sie identisch?

@ all: bin nicht auf die Idee gekommen auch mal die rechte Seite bissel umzuformen. werde das jetzt mal versuchen.

Ja, hab die 1-10 Klasse übersprungen, sollte ich deshalb mein Studium nun abbrechen, weil ich die Schulmathematik nicht mehr so drauf habe? das ist erbärmlich… mit Verlaub natürlich

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-21 17:25
T
Ja, hab die 1-10 Klasse übersprungen, sollte ich deshalb mein Studium nun abbrechen, weil ich die Schulmathematik nicht mehr so drauf habe? das ist erbärmlich… mit Verlaub natürlich
[14]

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-21 17:54
Alexander_W
so, habe jetzt etwas rumgespielt.

Wenn ich die Formel von Loom nun auf dem selben Nenner habe, schreibe ich sie so auf

[img]http://mokrates.de/cgi-bin/texstring?((n+1)*n*(n-1)+(n+1)*n*(n-1)*….*3)/2*1[/img]

doch was mach ich damit nun?

das Spielen mit der Formel (n+2) über (n-1) wie Slater das vorgeführt hat, kann ich irgendwie auch nicht weiter zu einem Ergebnis führen, welches mir was bringt.

Warum ich wissen will, warum das gleich ist? na wenn wieder so eine Aufgabe in der Klausur kommt, muss ich doch an irgenwas erkennen können, warum die Formeln gleich sind?!
durch diese Gleichung…
[img]http://mokrates.de/cgi-bin/texstring?{n%20\choose%20k}%20=%20{n-1%20\choose%20k-1}%20+%20{n-1%20\choose%20k}[/img]
…sehe ich leider nicht, dass sie gleich sind, weil sie nicht genau in der Form vorliegt. Woran soll ich sowas also erkennen?

ist ja nicht so, dass ich mir keine Mühe gegeben habe es zu lösen, ber egal wie ich es mache, es kommt nicht das raus was ich haben will


PS: das man das Ganze in der Klausur und so nicht ausrechnen muss, habe ich daran gesehen, weil eine Kommilitonin einfach geschrieben hatte, aufgrund von blablabla aus dem script ist das gleich. aber die Formel aus der Klausur passte nicht mit der Formel aus dem Ergebnis in der Klausur zusammen… das ist halt mein Problem gewesen, warum das als erklärung und volle Pktzahl trotzdem gereicht hat.

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-21 18:53
Slater
(n+1) über 2 ist nicht (n+1) * n * (n-1) * … * 3 / 2*1

bitte Definition nachschauen, Beispiel in Taschenrechner oder sonstwas

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-21 19:28
Alexander_W
ok, nun habe ich da

(n+1)*(n)*…..*(n-1)
____________
2*1

auch damit weiß ich erstmal nicht weiterzumachen.

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-21 20:18
T
der binomailkoeffizient ist definiert als: [latex]{n\choose k} := \frac {n!}{k! \cdot (n-k)!}[/latex]

[latex]{n+1 \choose n-2}=\frac{(n+1)!}{(n-2)!\cdot((n+1)-(n-2))!}[/latex] [latex]=\frac{(n+1)\cdot n \cdot (n-1) \cdot (n-2)!}{(n-2)! \cdot 3!}=\frac{(n+1)\cdot n \cdot (n-1)}{3!}[/latex] [latex]=\frac{(n^2+n)\cdot(n-1)}{6}=\frac{n^3-n^2+n^2-n}{6}=\frac 1 6 n^3 - \frac 1 6 n[/latex]


[latex]{n+1 \choose 2} = \frac{(n+1)!}{2!\cdot ((n+1)-2)!}[/latex] [latex]= \frac{(n+1) \cdot n \cdot (n-1)!}{2 \cdot (n-1)!} = \frac{(n+1) \cdot n}{2}[/latex] [latex]=\frac {n^2+n}{2} = \frac 1 2 n^2 + \frac 1 2 n[/latex]


[latex]{n+2 \choose n-1} = \frac{(n+2)!}{(n-1)! \cdot ((n+2)\cdot(n-1))!}[/latex] [latex]= \frac{(n+2)\cdot (n+1) \cdot n \cdot (n-1)!}{(n-1)! \cdot 3!} =\frac{(n+2)\cdot (n+1) \cdot n}{3!}[/latex] [latex] = \frac{(n^2 + n + 2n + 2) \cdot n}{6} = \frac {n^3+2n^2+2n}{6}[/latex] [latex] = \frac 1 6 n^3 + \frac 1 2 n^2 + \frac 1 3 n[/latex]

und siehe da:
[latex](\frac 1 6 n^3 - \frac 1 6 n) + (\frac 1 2 n^2 + \frac 1 2 n) = \frac 1 6 n^3 + \frac 1 2 n^2 + \frac 1 3 n[/latex]

[offtopic]
generell ist es hilfreich mit anderen zusammen zu lernen. (und natürlich auch die aufgaben während des semesters gemeinsam zu lösen). da wird oft einiges klarer.

und slater: wenn du nur vorhast hier zu behaupten das wäre alles pipifaxe, warum postest du dann hier überhaupt? es nutzt jedenfalls niemandem.
[/offtopic]

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-21 21:04
Alexander_W
danke sehr.

werde es mir morgen genauer ansehen und durchrechnen und mal schauen ob ich es auch hinbekomme, sonst bin ich nochmal hier :)

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-22 09:20
Slater
und slater: wenn du nur vorhast hier zu behaupten das wäre alles pipifaxe, warum postest du dann hier überhaupt? es nutzt jedenfalls niemandem.
ich poste nie Behauptungen oder Offtopic

die erste Antwort war bereits die vollständige Lösung,
die zweite bekräftigte bei Zweifeln nochmal den Rechenweg und die verwendeten Hilfsmittel,
die dritte reparierte eine festgefahrene Sackgasse

auf die Antwort von Alexander_W um 19.28 hätte ich ihn deutlich gebeten, auszumultiplizeren,
usw., das Ziel ist unausweichlich,

aus meinen Antworten lernt man auch wenn es vielleicht nicht der schöne einfache Weg ist :) ,
durch Vorsagen ist noch niemand schlau geworden

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-22 12:32
Loom
der binomailkoeffizient ist definiert als: [latex]{n\choose  k} := \frac {n!}{k! \cdot (n-k)!}[/latex]

Naja, in der Mathematik eher als
[latex]{n \choose k} := \frac{n \cdot (n -1 ) \cdot \dots \cdot (n - k + 1)}{k!}[/latex]

Woraus sich für ganze, positive n die obige Umformung ergibt [25]

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-22 18:58
Alexander_W
ok, meine erste Frage.

Im Bild habe ich eine Stelle rot markiert. Warum steht das Fakultätzeichen da? Fakultät ausklammern? dann hab ich was anderes und vor allem halt kein Fakultätszeichen mehr.

Und die Formeln im Script haben auch an der Stelle kein Fakultätszeichen.

danke im voraus :)
Anhänge m.jpg

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-22 19:15
Anonymer User
Du hast "vorher" (n+1)! im Zähler. Das heisst

(n+1)*n*(n-1)*(n-2)*(n-3)*….*3*2*1

Wenn du nun den Teil ab dem n-2 betrachtest, also (n-2)*(n-3)*…*3*2*1 dann ist
das gerade (n-2)! also steht im Zähler nichts anderes als

(n+1)*n*(n-1) * (n-2)! (lediglich eine andere Schreibweise für (n+1)! )

und das ist gerade das was "danach" im Zähler steht (bei dem Bruch, bei dem du
was rot markiert hattest).

Frank :)

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-23 18:05
Alexander_W
nun wird mir einiges klarer :)
habs nun auch geschafft.

danke euch allen

aber mir stellt sich jetzt noch eine Frage.
wie hätte ich auf anhieb erkennen sollen, dass diese Formeln wirklich gleich sind? aufgrund der Definition sehe ich das ja nicht (ihr schon?).

und das ganze ausrechnen hat man nicht die Zeit für. Und ich hab ja gesehen, dass es reicht, in der Klausur zu schreiben, dass die gleich sind aufgrund des Binomialkoeffizienten?!
muss ich ja aber erst selber sehen, dass sie gleich sind ;)

helft mir bitte :)

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-23 18:21
T
und das ganze ausrechnen hat man nicht die Zeit für. Und ich hab ja gesehen, dass es reicht,[…]
in der klausur musst du natürlich aufpassen dass du dich nicht in ein teilproblem vertieftst was zu lange dauert und wo du wohlmöglich dann doch keine lösung findest. wenn du annimmst eine gleichung würde gelten und du weisst grade nicht wie du das nachweisen kannst, schreib einfach dass sie gilt. wenn sie dann doch nicht gelten sollte kann alles was du daraus geschlossen hast als folgefehler gewertet werden. wenn du später noch zeit haben solltest kannst du dann ja noch versuchen die gleichheit zu beweisen.
und generell: wenn du bei einer aufgabe nach einem moment drüber nachdenken nicht weisst wie du das angehen sollst, such dir erstmal eine andere aufgabe.
viel spass bei der klausur.

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-23 20:32
UncleOwen
wie hätte ich auf anhieb erkennen sollen, dass diese Formeln wirklich gleich sind?

[latex]{n+1 \choose k+1} = {n \choose k} + {n \choose k+1}[/latex] Ist ein Satz ausm Skript (das ist das, was ich oben mit Additionstheorem meinte.)
[latex]{n'+2 \choose n'-1} = {n'+1 \choose n'-2} + {n'+1 \choose 2}[/latex] Das willst Du zeigen (Ich benenn das n mal um, damit's keine Verwirrung gibt).

Sieht doch schon ziemlich ähnlich aus. (Das muss man natürlich sehen. Wenn man das nicht sieht, hat man ein Problem.)
Jetzt versuchen wir mal, das passend zu machen. Damit's auf der linken Seite passt, müssen wir [latex]n := n'+1[/latex] und [latex]k := n'-2[/latex] setzen. Und siehe da: der jeweils erste Term auf der rechten Seite passt auch! Wenn jetzt also [latex]{n'+1 \choose 2} = {n'+1 \choose n'-1}[/latex] wäre, könnten wir obigen Satz anwenden. Und warum ist das gleich? Wegen der Symmetrie des Pascalschen Dreiecks, oder in Formel: [latex]{n \choose k} = {n \choose n-k}[/latex]

RE: Wie löse ich diese Aufgabe? Induktion! 2008-03-25 13:27
Alexander_W
danke euch allein für euren Einsatz hier.

Hat wohl dennoch trotzdem nicht gereicht. Mal sehen, vielleicht bin ich ja knapp durch.

war voll schwer die Klausur :(