Induktion / Umformungsschritt

24.04.2012, 15:06

rawfood

Auf diesen Beitrag antworten »

Induktion / Umformungsschritt

Hi Leute,

Ich stoße schon wieder an meine Grenzen.

$\begin{eqnarray*} (1+x) \sum_{k=0}^{n-1}\binom{n-1}{k}x^{k}= \sum_{k=0}^{n-1}x^{k}+\sum_{k=0}^{n-1}x^{k+1} \end{eqnarray*}$

Aus diesem Umformungsschritt werde ich nicht schlau. Hoffe ihr könnt mir helfen. Sollte dies nicht ausreichend sein, werd ich die komplette Aufgabe in Latex übersetzen.

Bin total gefrustet
Danke
Rawfood

24.04.2012, 15:45

rawfood

Auf diesen Beitrag antworten »

$\begin{eqnarray*} (1+x) \sum_{k=0}^{n-1}\binom{n-1}{k}x^{k}= \sum_{k=0}^{n-1}\binom{n-1}{k}x^{k}+\sum_{k=0}^{n-1}\binom{n-1}{k}x^{k+1} \end{eqnarray*}$

Mist, habs nicht mal richtig abgeschrieben....

So ist es gemeint, verstehe nicht warum der Exponent x^(k+1) zustande kommt ..

24.04.2012, 15:53

Helferlein

Auf diesen Beitrag antworten »

Dann multipliziere doch mal die linke Seite der Gleichung aus Augenzwinkern

Augenzwinkern

26.04.2012, 12:58

rawfood

Auf diesen Beitrag antworten »

Danke Helferlein,

Auf die Idee einfach mal den Ausdruck mit der Summe als normales Produkt zu behandeln bin ich nicht gekommen.

$\begin{eqnarray*} \binom{n-1}{0}+\sum_{k=1}^{n-1} \bigg(\binom{n-1}{k}+\binom{n-1}{k-1}\bigg)x^{k}+\binom{n-1}{n-1}x^{n} =1+\sum_{k=1}^{n-1}\binom{n}{k}x^{k}+x^{n} \end{eqnarray*}$

Ich verstehe noch nicht warum n-1 über k addiert mit n-1 über k-1 multipliziert mit x hoch k zu n über k wird.... Der Rest ist mir klar n-1 über 0 wird zu 1, und n-1 über n-1 wiederum auch zu eins...

Danke
Rawfood

26.04.2012, 13:01

Helferlein

Auf diesen Beitrag antworten »

Das ist nicht ganz das, was ich meinte:

$\begin{eqnarray*} (1+x) \sum_{k=0}^{n-1}\binom{n-1}{k}x^{k}= 1\cdot \sum_{k=0}^{n-1}\binom{n-1}{k}x^{k} + x\cdot \sum_{k=0}^{n-1}\binom{n-1}{k}x^{k} \end{eqnarray*}$

26.04.2012, 15:02

HAL 9000

Auf diesen Beitrag antworten »

Ich denke, rawfood ist schon zur übernächsten Zeile der Gleichungsumformung gesprungen, die er jetzt Zeile für Zeile zwecks Verständnisses durchgeht. Wäre schön gewesen, das auch mitzuteilen...

Anzeige

26.04.2012, 15:23

Helferlein

Auf diesen Beitrag antworten »

Danke für den Hinweis, HAL smile

smile

@rawfood:
Das ist einfach nur ein Rechengesetz für Binomialkoeffizienten, kann aber zur Not auch durch Einsetzen der Definition nachgewiesen werden:

$\begin{eqnarray*} \binom{n-1}{k}+\binom{n-1}{k-1} = \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}<br /> <br /> = \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!(n-k)!} = \frac{n!}{k!(n-k)!}\left(\frac{n-k}n+\frac kn\right) \end{eqnarray*}$

28.04.2012, 12:49

rawfood

Auf diesen Beitrag antworten »

Danke für die Hilfe.

Ich widme mich gerade folgender Aufgabe :

Ich soll Korollar 2.3.8 beweisen: $\begin{eqnarray*} (a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k} \end{eqnarray*}$

Ich vermute mal, dass es analog zum obigen Beweis funktioniert:

Hier mal meine folgenden Schritte

$\begin{eqnarray*} (a+b)^{n}=(a+b)(a+b)^{n-1} \end{eqnarray*}$

$\begin{eqnarray*} (a+b)^{n-1}=\sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{(n-1)-k} \end{eqnarray*}$

nach IV

$\begin{eqnarray*} (a+b)^{n}=(a+b)\sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{(n-1)-k} \end{eqnarray*}$

$\begin{eqnarray*} =\sum_{k=0}^{n-1}\binom{n-1}{k}a^{k+1}b^{(n-1)-k}+ \sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{n-k}<br /> <br /> \end{eqnarray*}$

$\begin{eqnarray*} =\sum_{k=1}^{n}\binom{n-1}{k-1}a^{k}b^{(n-1)-(k-1)}+ \sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$

Im Beweis im Skript wurde eine Indexverschiebung durchgeführt. Der Startindex sowie der Endindex wurden um 1 Wert angehoben. Ohne zu verstehen, ob mir dieser Schritt hier auch nützlich ist, habe ich es gemacht. Die Frage ist allerdings : Brauch ich das überhaupt? Und wenn ich den Index erhöhe, warum werden dann zwar alle Werte von k erniedrigt, aber die Werte die von n abghängig sind, nicht? Oder anders, wenn ich eine Indexverschiebung durchführe, woher weiß ich welchen Exponenten ich wie anpassen muss?

Danke
Rawfood

28.04.2012, 15:10

Helferlein

Auf diesen Beitrag antworten »

Eine Indexverschiebung betrifft natürlich nur den Index selbst, denn nur der ändert sich bei der Verschiebung.
Eine Verschiebung ist ja nichts anderes als eine Substitution der Art j=k+1.

28.04.2012, 17:15

rawfood

Auf diesen Beitrag antworten »

Okay, j = k+1, memoriert smile

smile

Und was ist mit meinen Umformungen? Taugen die soweit?

28.04.2012, 18:30

Helferlein

Auf diesen Beitrag antworten »

ja, das sieht gut aus.

30.04.2012, 12:53

rawfood

Auf diesen Beitrag antworten »

So, die letzten Tage habe ich nichts mehr gemacht. Dazu bin ich, wenn ich was mache ziemlich langsam. Gibts irgendein Medikament gegen eine lange Leitung? Big Laugh

Big Laugh

So, mein nächster Umformungsschritt sieht so aus:
Von : $\begin{eqnarray*} =\sum_{k=1}^{n}\binom{n-1}{k-1}a^{k}b^{(n-1)-(k-1)}+ \sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$
zu:
$\begin{eqnarray*} = \sum_{k=1}^{n-1}\binom{n-1}{k-1}a^{k}b^{n-k}+\binom{n-1}{n-1}a^{n}+\binom{n-1}{0}+\sum_{k=1}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$

Ich verstehe dabei überhaupt nicht was ich tue. Sondern wende einfach die Umformungsschritte aus dem Beweis der analog zu funktionieren scheint an.

Sagt mir, wenn es korrekt oder falsch ist.

Danke
Rawfood

02.05.2012, 17:50

rawfood

Auf diesen Beitrag antworten »

So ich war weiter aktiv:

So siehts nun aus :

$\begin{eqnarray*} \sum_{k=1}^{n-1}\binom{n-1}{k-1}a^{k}b^{n-k}+\binom{n-1}{n-1}a^{n}+\binom{n-1}{0}+\sum_{k=1}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$

$\begin{eqnarray*} =\binom{n-1}{0}+ \sum_{k=1}^{n-1}\bigg(\binom{n-1}{k}+\binom{n-1}{k-1}\bigg)a^{k}b^{n-k} +\binom{n-1}{n-1}a^{n} \end{eqnarray*}$

$\begin{eqnarray*} =1+\sum_{k=1}^{n-1} \binom{n}{k}a^{k}b^{n-k}+a^{n} \end{eqnarray*}$

$\begin{eqnarray*} =\sum_{k=0}^{n} \binom{n}{k}a^{k}b^{n-k} \end{eqnarray*}$

Ich war jetzt gerade weiter an der Aufgabe dran. Tue mich mit Mathematik sehr schwer. Auch wenn im Skript eine analoge Aufgabe vorkommt. Für mich war vieles Unklar, und wenn dies so richtig ist, dann war dies die erste Aufgabe wo ich dachte, dass schaffe ich niemals die ich selbstständig mit ein wenig Support von euch gelöst habe. Sollte dies so richtig sein, dann beantwortet mir bitte die Frage wo das a^n hin ist. Und warum die Indizes von 1 auf 0 sinken und von n-1 auf n steigen. Dies ist mir nicht ganz klar, nehme an das hat was mit der 1 vor dem Summenzeichen und dem a^n zu tun.

Danke
Rawfood

02.05.2012, 21:02

Hellsing91

Auf diesen Beitrag antworten »

Zitat:

Von : $\begin{eqnarray*} =\sum_{k=1}^{n}\binom{n-1}{k-1}a^{k}b^{(n-1)-(k-1)}+ \sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$ zu: $\begin{eqnarray*} = \sum_{k=1}^{n-1}\binom{n-1}{k-1}a^{k}b^{n-k}+\binom{n-1}{n-1}a^{n}+\binom{n-1}{0}+\sum_{k=1}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$

Hier ist ein Fehler, dort fehlt mal b^n siehst du das ?

Zitat:

Ich verstehe dabei überhaupt nicht was ich tue. Sondern wende einfach die Umformungsschritte aus dem Beweis der analog zu funktionieren scheint an.

Also das du weisst was du tust ist natürlich auch wichtig.
Hier hast du z.B. für die Linke Summe einmal n eingesetzt. Dadurch geht die Summe natürlich nur noch bis n-1, da du ja für n eingesetzt wieder addierst also den hier $\begin{eqnarray*} \binom{n-1}{n-1}a^{n} \end{eqnarray*}$ (Einfach n eingesetzt). Analog natürlich auch auf der rechten Seite dort hast du nur 0 eingestzt für k, dies zur Summe addiert weswegen sie nun bei k=1 losgeht.

Der Sinn ist es auf den gleichen Index zu kommen.

Der flüchtige blick hierdrauf:

Zitat:

So siehts nun aus : $\begin{eqnarray*} \sum_{k=1}^{n-1}\binom{n-1}{k-1}a^{k}b^{n-k}+\binom{n-1}{n-1}a^{n}+\binom{n-1}{0}+\sum_{k=1}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$ $\begin{eqnarray*} =\binom{n-1}{0}+ \sum_{k=1}^{n-1}\bigg(\binom{n-1}{k}+\binom{n-1}{k-1}\bigg)a^{k}b^{n-k} +\binom{n-1}{n-1}a^{n} \end{eqnarray*}$ $\begin{eqnarray*} =1+\sum_{k=1}^{n-1} \binom{n}{k}a^{k}b^{n-k}+a^{n} \end{eqnarray*}$ $\begin{eqnarray*} =\sum_{k=0}^{n} \binom{n}{k}a^{k}b^{n-k} \end{eqnarray*}$

Bis zur zweiten Zeile sieht es gut aus. Es ist ja nicht viel passiert. Einfach nur umsortiert und ausgeklammert (also die Summe ausgeklammert, mit den Bino.). In der dritten Zeile wurden dann die Additionstheoreme angewandt.

Kommen wir also zur letzten Zeile:

Zitat:

dann beantwortet mir bitte die Frage wo das a^n hin ist. Und warum die Indizes von 1 auf 0 sinken und von n-1 auf n steigen. Dies ist mir nicht ganz klar, nehme an das hat was mit der 1 vor dem Summenzeichen und dem a^n zu tun.

Was passiert denn wenn du für die letzte Summe einmal k=0, und einmal k=n einsetzt ?

Dann solltest du das schon sehen smile

smile

Allerdings sieht mir da grade etwas falsch aus, bzw. fehlt da irgendwo ein b^n. Kann aber auch sein das ich mich verguckt habe, ich schau nochmal alles durch.

Edit: Ich kann verstehen wenn man zwischendurch rucksprache haben möchte, ob das gerechnete stimmt. Es ist aber sinvoller erstmal das ganze zu rechnen, und dann später wenn du fertig bist dein Ergebnis hier korrigieren zu lassen.

Das ganze wird sonst sehr unübersichtlich.

03.05.2012, 01:20

rawfood

Auf diesen Beitrag antworten »

Zitat:

Original von Hellsing91
[QUOTE]Von : $\begin{eqnarray*} =\sum_{k=1}^{n}\binom{n-1}{k-1}a^{k}b^{(n-1)-(k-1)}+ \sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$ zu: $\begin{eqnarray*} = \sum_{k=1}^{n-1}\binom{n-1}{k-1}a^{k}b^{n-k}+\binom{n-1}{n-1}a^{n}+\binom{n-1}{0}+\sum_{k=1}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$

Hier ist ein Fehler, dort fehlt mal b^n siehst du das ?
Ich dachte, dass b hoch n - k gleich b hoch n -n ist, was b hoch 0 ergibt, und somit 1... nicht?

Wenn ich jetzt nicht totalen Bockmist baue, dann ist für k=0 der Ausdruck 1, und für k=n der Ausdruck a^n...

Ich schaue morgen nochmal drüber. Jetzt ist es bissel spät. Danke!!!

03.05.2012, 13:45

Hellsing91

Auf diesen Beitrag antworten »

Zitat:

Ich dachte, dass b hoch n - k gleich b hoch n -n ist, was b hoch 0 ergibt, und somit 1... nicht?

Wofür genau meinst du jetz. Also du setzt für k=n ein. Ja dann kommt da $\begin{eqnarray*} b^{n-n} \end{eqnarray*}$ =1 raus.

Der Term $\begin{eqnarray*} \binom{n-1}{n-1}a^{n} \end{eqnarray*}$ ist ja auch korrekt.

Es geht hier aber um diesen Ausdruck:

$\begin{eqnarray*} \binom{n-1}{0} \end{eqnarray*}$

Den erhälst du wenn du hier:

$\begin{eqnarray*} \sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$

einmal k=0 einsetzt.

Damit erhälst du:

$\begin{eqnarray*} \binom{n-1}{0}a^{0}b^{n-0} \end{eqnarray*}$

Da aber $\begin{eqnarray*} a^{0}=1 \end{eqnarray*}$ ist, und $\begin{eqnarray*} b^{n-0}=b^n \end{eqnarray*}$

müsste dort korrekt stehen:

$\begin{eqnarray*} \binom{n-1}{0}b^n \end{eqnarray*}$

hier nochmal der ganze ausdruck korrigiert:

Von :
$\begin{eqnarray*} =\sum_{k=1}^{n}\binom{n-1}{k-1}a^{k}b^{(n-1)-(k-1)}+ \sum_{k=0}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$

zu:
$\begin{eqnarray*} = \sum_{k=1}^{n-1}\binom{n-1}{k-1}a^{k}b^{n-k}+\binom{n-1}{n-1}a^{n}+\binom{n-1}{0}b^{n}+\sum_{k=1}^{n-1}\binom{n-1}{k}a^{k}b^{n-k} \end{eqnarray*}$

Das du das du $\begin{eqnarray*} b^n \end{eqnarray*}$ benötigst, siehst du auch wenn du in den letzten Term also:

$\begin{eqnarray*} =\sum_{k=0}^{n} \binom{n}{k}a^{k}b^{n-k} \end{eqnarray*}$

mal k=0 einsetzt.

mfg. Hellsing Augenzwinkern

Augenzwinkern

03.05.2012, 15:35

rawfood

Auf diesen Beitrag antworten »

Vielen lieben Dank für deine ausführliche Erklärung!!! Ich schaus mir jetzt mal genauer an, und werde alles genau nachvollziehen, damit ich solche Fehler in Zukunft vermeide.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »