vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:21 Mi 01.11.2006 | | Autor: | Phoney |
| Aufgabe | | Beweisen Sie, dass [mm] $\vektor{x+y\\n}=\summe_{k=0}^{n}\vektor{x\\n-k}\vektor{y\\k}$ [/mm] |
Hallo Leute.
Ich soll das oben beweisen. Nun habe ich erst einen Blick in meine Formelsammlung geworfen und dabei dir Formeln
[mm] $\vektor{n\\k}=\br{n!}{(n-k)!*k!} [/mm] $
sowie
[mm] $\vektor{x\\k}=\produkt_{j=1}^{k}\br{x-j+1}{j}$
[/mm]
gefunden.
Ich wüsste jetzt aber so nicht, was ich damit anfangen könnte. Also probiere ich es mit vollständiger Induktion. Zunächst einmal setze ich in die Formel oben stumpf für n eins ein.
[mm] $\vektor{x+y\\1}=\summe_{k=0}^{1}\vektor{x\\n-k}\vektor{y\\k}$
[/mm]
[mm] $\vektor{x+y\\1}=\br{x!}{(x-n)!*n!}*1+\br{x!}{(x-n+1)!*(n-1)!}*\br{y!}{(y-1)!*1!}$
[/mm]
Das ist jetzt aber nicht wirklich
[mm] $\br{(x+y)!}{(x+y-1)!*1!}=\br{x!}{(x-n)!*n!}*1+\br{x!}{(x-n+1)!*(n-1)!}*\br{y!}{(y-1)!*1!}$
[/mm]
Bin also auf dem falschen Dampfer.
Was genau muss ich denn machen? Hat das überhaupt etwas mit vollständiger Induktion zu tun?
Schöne Grüße
Johann
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:54 Mi 01.11.2006 | | Autor: | Bastiane |
Hallo Phoney,
hab' die Aufgabe nur kurz überflogen, aber ich glaube schon, dass das mit vollständiger Induktion zu beweisen ist. Und ähnliche Beweise findest du auch hier im Forum, evtl. sogar genau diesen. Such doch mal ein bisschen, wahrscheinlich am besten unter dem Stichwort "Vollständige Induktion".
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:40 Fr 03.11.2006 | | Autor: | Phoney |
| Aufgabe | | Beweisen Sie, dass $ [mm] \vektor{x+y\\n}=\summe_{k=0}^{n}\vektor{x\\n-k}\vektor{y\\k} [/mm] $ |
Mojn.
Mittlerweile bin ich etwas weiter.
Nämlich schon für n+1.
ich muss jetzt also zeigen, dass
[mm] $\vektor{x+y\\n+1}=\summe_{k=0}^{n+1}\vektor{x\\n-k}\vektor{y\\k} [/mm] $
Für k=0 bis n wissen wir ja, dass es [mm] \vektor{x+y\\n} [/mm] ist.
Das setze ich da jetzt ein
[mm] $\vektor{x+y\\n+1}=\vektor{x+y\\n}+\red{\vektor{x\\n+1-n-1}*\vektor{y\\n+1}}$
[/mm]
Also hier beim roten habe ich für n eingesetzt: n+1
ebenfalls für k -> n+1
Ausprobieren zeigt mir das ist definitiv nicht das selbe
Gruß,
Johann
|
|
|
| |
|
> Beweisen Sie, dass
> [mm]\vektor{x+y\\n}=\summe_{k=0}^{n}\vektor{x\\n-k}\vektor{y\\k}[/mm]
> Mojn.
>
> Mittlerweile bin ich etwas weiter.
>
> Nämlich schon für n+1.
>
> ich muss jetzt also zeigen, dass
>
> [mm]\vektor{x+y\\n+1}=\summe_{k=0}^{n+1}\vektor{x\\n-k}\vektor{y\\k}[/mm]
>
Hallo,
und : nein!
Du mußt zeigen, daß [mm] \vektor{x+y\\n+1}=\summe_{k=0}^{n+1}\vektor{x\\ n+1-k}\vektor{y\\k} [/mm] gilt.
Du hast ein n vergessen durch n+1 zu ersetzen.
Möglicherweise klärt sich nun alles.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:09 Fr 03.11.2006 | | Autor: | Phoney |
Hallo.
Danke für die Antwort, doch irgendwie läufts bei mir immer noch nicht so richtig rund
$ [mm] \vektor{x+y\\n+1}=\summe_{k=0}^{n+1}\vektor{x\\ n+1-k}\vektor{y\\k} [/mm] $
bedeutet, dass
$ [mm] \vektor{x+y\\n+1}=\summe_{k=0}^{n} \vektor{x\\ n+1-k}\vektor{y\\k}+\vektor{x\\ (n+1)+1-(n+1)}\vektor{y\\(n+1)} [/mm] $
Ixh glaube, so ganz habe ich das leider noch nicht verstanden. Interpretier ich denn den letzten rechenschritt richtig?
Gruß
Johann
|
|
|
| |
|
Hallo Phoney,
> Danke für die Antwort, doch irgendwie läufts bei mir immer
> noch nicht so richtig rund
>
> [mm]\vektor{x+y\\n+1}=\summe_{k=0}^{n+1}\vektor{x\\ n+1-k}\vektor{y\\k}[/mm]
>
> bedeutet, dass
>
> [mm]\vektor{x+y\\n+1}=\summe_{k=0}^{n} \vektor{x\\ n+1-k}\vektor{y\\k}+\vektor{x\\ (n+1)+1-(n+1)}\vektor{y\\(n+1)}[/mm]
>
> Ixh glaube, so ganz habe ich das leider noch nicht
> verstanden. Interpretier ich denn den letzten rechenschritt
> richtig?
Nicht ganz. Du zerlegst ja jetzt deine Summe von 1 bis n+1 in die Summe von 1 bis n plus den Summanden, für den gilt: k=n+1. Da musst du dann aber alles beibehalten, nur für k musst du n+1 einsetzen. Nicht aber noch einmal für n. Das sieht also dann so aus:
[mm] \vektor{x+y\\n+1}=\summe_{k=0}^{n} \vektor{x\\ n+1-k}\vektor{y\\k}+\vektor{x\\ n+1-(n+1)}\vektor{y\\(n+1)}
[/mm]
Wie man das allerdings jetzt zeigt, habe ich auf die Schnelle nicht hinbekommen. Evtl. braucht man da noch eine Eigenschaft des Binomialkoeffizienten. Habt ihr da vielleicht in einer anderen Aufgabe oder auf einem anderen Übungsblatt schon etwas bewiesen? Das könnte hilfreich sein.
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:14 Fr 03.11.2006 | | Autor: | Phoney |
Seid gegrüßt
Zunächst einmal danke für die fleißige Hilfestellung.
> Nicht ganz. Du zerlegst ja jetzt deine Summe von 1 bis n+1
> in die Summe von 1 bis n plus den Summanden, für den gilt:
> k=n+1. Da musst du dann aber alles beibehalten, nur für k
> musst du n+1 einsetzen. Nicht aber noch einmal für n. Das
> sieht also dann so aus:
>
> [mm]\vektor{x+y\\n+1}=\summe_{k=0}^{n} \vektor{x\\ n+1-k}\vektor{y\\k}+\vektor{x\\ n+1-(n+1)}\vektor{y\\(n+1)}[/mm]
Was setze ich denn für k ein? Oder womit ersetze ich den [mm] \Vektor\summe_{k=0}^{n} \vektor{x\\ n+1-k}\vektor{y\\k}
[/mm]
?
Ich muss das leider so frech fragen, ich habe da nämlich keinen blaßen Schimmer. Normalerweise hätte ich ja x+y über n eingesetzt...aber wegen dem n+1 geht das ja nicht mehr :(
>
> Wie man das allerdings jetzt zeigt, habe ich auf die
> Schnelle nicht hinbekommen. Evtl. braucht man da noch eine
Ja, das ist aber auch eine harte Nuss.
Wobei ich mich damit ja schon über längere Zeit beschäftige.
> Eigenschaft des Binomialkoeffizienten. Habt ihr da
> vielleicht in einer anderen Aufgabe oder auf einem anderen
> Übungsblatt schon etwas bewiesen? Das könnte hilfreich
> sein.
Das ist Aufg 1
Und mehr als zwei Aufgaben sind es auch nicht auf dem Zettel...Die andere Aufgabe gehört zu den Summenformeln, die zu beweisen.
Phoney
|
|
|
| |
|
Zunächst gilt für alle [mm] a\in\IR [/mm] und [mm] m\in\IN [/mm] die Beziehung
[mm] \vektor{a\\m} [/mm] = [mm] \bruch{\produkt_{i=1}^{m}(a+1-i)}{m!}
[/mm]
Nun zum Beweis mittels vollständiger Induktion.
Induktionsanfang: n=0: [mm] \vektor{x+y\\0} [/mm] = 1 = 1*1 = [mm] \vektor{x\\0}*\vektor{y\\0} [/mm] = [mm] \summe_{k=0}^{0}\vektor{x\\0-k}*\vektor{y\\k}
[/mm]
Es gilt:
[mm] \vektor{x+y\\n+1} [/mm] = [mm] \bruch{\produkt_{i=1}^{n+1}(x+y+1-i)}{(n+1)!}
[/mm]
= [mm] \bruch{x+y-n}{n+1} [/mm] * [mm] \bruch{\produkt_{i=1}^{n}(x+y+1-i)}{n!}
[/mm]
= [mm] \bruch{x+y-n}{n+1} [/mm] * [mm] \vektor{x+y\\n}
[/mm]
Verwende nun die Induktionsvoraussetzung
[mm] \vektor{x+y\\n} [/mm] = [mm] \summe_{k=0}^{n}\vektor{x\\n-k}*\vektor{y\\k}
[/mm]
Dann folgt weiter:
[mm] \vektor{x+y\\n+1} [/mm] = [mm] \bruch{x+y-n}{n+1} [/mm] * [mm] \summe_{k=0}^{n}\vektor{x\\n-k}*\vektor{y\\k}
[/mm]
= [mm] \bruch{x+y-n}{n+1} [/mm] * [mm] \summe_{k=0}^{n}(\bruch{\produkt_{i=1}^{n-k}(x+1-i)}{(n-k)!}*\bruch{\produkt_{i=1}^{k}(y+1-i)}{k!})
[/mm]
= [mm] \summe_{k=0}^{n}(\bruch{(x + 1 - (n+1-k)) + (y + 1 - (k+1))}{n+1}*\bruch{\produkt_{i=1}^{n-k}(x+1-i)}{(n-k)!}*\bruch{\produkt_{i=1}^{k}(y+1-i)}{k!})
[/mm]
= [mm] \summe_{k=0}^{n}(\bruch{1}{n+1}*\bruch{\produkt_{i=1}^{n+1-k}(x+1-i)}{(n-k)!}*\bruch{\produkt_{i=1}^{k}(y+1-i)}{k!}) [/mm] + [mm] \summe_{k=0}^{n}(\bruch{1}{n+1}*\bruch{\produkt_{i=1}^{n-k}(x+1-i)}{(n-k)!}*\bruch{\produkt_{i=1}^{k+1}(y+1-i)}{k!})
[/mm]
= [mm] \bruch{1}{n+1}*\bruch{\produkt_{i=1}^{n+1}(x+1-i)}{n!} [/mm] + [mm] \summe_{k=1}^{n}(\bruch{n+1-k}{n+1}*\bruch{\produkt_{i=1}^{n+1-k}(x+1-i)}{(n+1-k)!}*\bruch{\produkt_{i=1}^{k}(y+1-i)}{k!}) [/mm] + [mm] \summe_{k=0}^{n-1}(\bruch{k+1}{n+1}*\bruch{\produkt_{i=1}^{n-k}(x+1-i)}{(n-k)!}*\bruch{\produkt_{i=1}^{k+1}(y+1-i)}{(k+1)!}) [/mm] + [mm] \bruch{1}{n+1}*\bruch{\produkt_{i=1}^{n+1}(y+1-i)}{n!}
[/mm]
= [mm] \bruch{\produkt_{i=1}^{n+1}(x+1-i)}{(n+1)!} [/mm] + [mm] \summe_{k=1}^{n}(\bruch{n+1-k}{n+1}*\bruch{\produkt_{i=1}^{n+1-k}(x+1-i)}{(n+1-k)!}*\bruch{\produkt_{i=1}^{k}(y+1-i)}{k!}) [/mm] + [mm] \summe_{k=1}^{n}(\bruch{k}{n+1}*\bruch{\produkt_{i=1}^{n+1-k}(x+1-i)}{(n+1-k)!}*\bruch{\produkt_{i=1}^{k}(y+1-i)}{k!}) [/mm] + [mm] \bruch{\produkt_{i=1}^{n+1}(y+1-i)}{(n+1)!}
[/mm]
= [mm] \vektor{x\\n+1} [/mm] + [mm] \summe_{k=1}^{n}((\bruch{n+1-k}{n+1}+\bruch{k}{n+1})*\bruch{\produkt_{i=1}^{n+1-k}(x+1-i)}{(n+1-k)!}*\bruch{\produkt_{i=1}^{k}(y+1-i)}{k!}) [/mm] + [mm] \vektor{y\\n+1}
[/mm]
= [mm] \vektor{x\\n+1}*\vektor{y\\0} [/mm] + [mm] \summe_{k=1}^{n}1*\vektor{x\\n+1-k}*\vektor{y\\k}) [/mm] + [mm] \vektor{x\\0}*\vektor{y\\n+1}
[/mm]
= [mm] \summe_{k=0}^{n+1}(\vektor{x\\n+1-k}*\vektor{y\\k})
[/mm]
qed
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:09 Do 16.11.2006 | | Autor: | Phoney |
Hallo otto.euler.
Das war eine der genialsten Antworten, die ich hier jemals gelesen habe. Hat sicherlich sehr lange gedauert, das hier alles zu tippen...umso schwieriger für mich, meinen Dank dir gegenüber (natürlich hatten mir auch die anderen etwas geholfen) zu formulieren.
Also, vielen vielen vielen vielen Dank dafür!
Das hilft mir wirklich sehr gut. Danke!
Beste Grüße,
Johann
|
|
|
|
