vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:01 So 23.03.2008 | | Autor: | penguin |
| Aufgabe | Man zeige: für alle [mm] n\in\IN [/mm] gilt
[mm] \vektor{2n \\ n} [/mm] = [mm] \summe_{k=0}^{n} \vektor{n \\ k}^2
[/mm]
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. |
Also ich wollte diese Aufgabe durch Induktion lösen. d.h
I.A: n=1 und kriege dann durch einsetzten 2=2 raus.
I.S: [mm] n\ton+1
[/mm]
I.V: [mm] \vektor{2n \\ n} [/mm] = [mm] \summe_{k=0}^{n} \vektor{n \\ k}^2
[/mm]
und jetzt bei der Induktionsbehauptung, da bin ich mir nicht ganz sicher, ob ich für jedes einzelne n=n+1 einsetzen muss. Ich hab da nämlich 2 Ideen, ich bin mir nur nicht sicher, welche richtig ist, also ich dachte mir, ich schreib mal beide auf und vielleicht wäre jemand so nett mir zu sagen, welcher der richtige Ansatz ist, denn wie man das ausrechnet ist mir klar, nur beim Ansatz haperts ein bisschen.
[mm] \vektor{2n +2 \\ n+1} [/mm] = [mm] \summe_{k=0}^{n+1} \vektor{n \\ k}^2
[/mm]
oder [mm] \vektor{2n +2 \\ n+1} [/mm] = [mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ k}^2
[/mm]
Also wäre echt super nett wenn mir jemand helfen könnte
lg penguin
|
|
| |
|
Hallo penguin,
(Ersteinmal direkt zur Frage: Jedes n muss durch n+1 ersetzt werden!)
Die Idee mit der vollständigen Induktion ist nicht übel.
Beim eigentlichen Induktionsbeweis sollte man immer so vorgehen, dass man von der linken Seite anfängt, diese dann so umformt dass man die Induktionsvoraussetzung anwenden kann und danach zielstrebig versucht, den Term in Gleichheit mit der rechten Seite zu bringen.
Bei dir sähe das folgendermaßen aus:
Wir haben
[mm] \vektor{2n+2 \\ n+1}
[/mm]
Bestimmt habt ihr nun tolle Umformungen für Binomialkoeffizienten kennen gelernt. Versuche, den obigen in eine Form
[mm] \vektor{2n+2 \\ n+1} [/mm] = ... = [mm] \vektor{2n \\ n} [/mm] + ...
zu bringen. Wende dann die Induktionsvoraussetzung an und poste dein Zwischenergebnis 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:51 Mo 24.03.2008 | | Autor: | penguin |
Also ist meine Induktionsbehauptung
[mm] \vektor{2n+2 \\ n+1} [/mm] = [mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ k}^2
[/mm]
und dann kann ich doch sagen, dass
[mm] \vektor{2n+2 \\ n+1} [/mm] = [mm] \bruch{(2n+2)!}{(n+1)!(n+1)!} [/mm] und dann bin ich mir nicht ganz sicher wie ich das weiterumformen muss, aber ich bin mir ziemlich sicher, dass am Ende, wenn man die Additionsformel benutzt,
[mm] \vektor{2n \\ n} [/mm] + [mm] \vektor{2n+1 \\ n+1} [/mm] rauskommen sollte (hoffe ich auf jedenfall  ) und dann kann ich meine Induktionsvoraussetzung benutzen und sagen
[mm] \vektor{2n \\ n} [/mm] + [mm] \vektor{2n+1 \\ n+1} [/mm] = (nach der I.V) [mm] \summe_{k=0}^{n} \vektor{n \\ k}^2 [/mm] + [mm] \vektor{2n+1 \\ n+1} [/mm] und dann muss ich das noch irgendwie zusammenfassen,sodass ich dann [mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ k}^2 [/mm] rauskriege. Lieg ich soweit jetzt richtig...
thx für deine Hilfe penguin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:29 Mo 24.03.2008 | | Autor: | abakus |
> Also ist meine Induktionsbehauptung
>
> [mm]\vektor{2n+2 \\ n+1}[/mm] = [mm]\summe_{k=0}^{n+1} \vektor{n+1 \\ k}^2[/mm]
>
> und dann kann ich doch sagen, dass
... unter anderem auch [mm] \vektor{n+1 \\ k}=\vektor{n \\ k-1}+\vektor{n\\ k} [/mm] ist und demzufolge
[mm] \vektor{n+1 \\ k}^2=\vektor{n \\ k-1}^2+ 2\vektor{n \\ k-1}*\vektor{n\\ k}+\vektor{n\\ k}^2
[/mm]
ist.
Das hat zumindest den Vorteil, dass die Summe der letzten Summanden [mm] \vektor{n\\ k}^2 [/mm] bereits in der Induktionsvoraussetzung drin war und der Rest jetzt noch dazukommt.
Gruß Abakus
>
>
> [mm]\vektor{2n+2 \\ n+1}[/mm] = [mm]\bruch{(2n+2)!}{(n+1)!(n+1)!}[/mm] und
> dann bin ich mir nicht ganz sicher wie ich das
> weiterumformen muss, aber ich bin mir ziemlich sicher, dass
> am Ende, wenn man die Additionsformel benutzt,
>
> [mm]\vektor{2n \\ n}[/mm] + [mm]\vektor{2n+1 \\ n+1}[/mm] rauskommen sollte
> (hoffe ich auf jedenfall ) und dann kann ich meine
> Induktionsvoraussetzung benutzen und sagen
>
> [mm]\vektor{2n \\ n}[/mm] + [mm]\vektor{2n+1 \\ n+1}[/mm] = (nach der I.V)
> [mm]\summe_{k=0}^{n} \vektor{n \\ k}^2[/mm] + [mm]\vektor{2n+1 \\ n+1}[/mm]
> und dann muss ich das noch irgendwie zusammenfassen,sodass
> ich dann [mm]\summe_{k=0}^{n+1} \vektor{n+1 \\ k}^2[/mm] rauskriege.
> Lieg ich soweit jetzt richtig...
>
> thx für deine Hilfe penguin
|
|
|
| |
|
Ich halte es für schwer, diese Formel durch Induktion nachzuweisen. Ich schlage einen kombinatorischen Ansatz vor.
Stelle dir eine Gruppe aus [mm]n[/mm] Männern und [mm]n[/mm] Frauen vor. Aus diesen [mm]2n[/mm] Personen werden nun [mm]n[/mm] ausgelost.
a) Wie viele Möglichkeiten gibt es dafür insgesamt?
b) Bei wie vielen der Möglichkeiten aus a) ist kein Mann beteiligt?
... ist genau ein Mann beteiligt?
... sind genau zwei Männer beteiligt?
...
... sind genau [mm]n[/mm] Männer beteiligt?
Und wie erhält man jetzt aus a) und b) die gesuchte Formel?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:58 Mo 24.03.2008 | | Autor: | DaMazen |
Wenn Induktion, muss man hier wohl zwei Induktionen machen, eine nach k und eine nach n:
Also nach n:
Für ein festes k gelte.....
und so eben auch nach k...
wenn sich beide beweisen lassen ist die gesamte Behauptung durch Induktion bewiesen.
Ichdenke aber auh ein direkter Beweis macht die Sache viel leichter.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:48 Mo 24.03.2008 | | Autor: | penguin |
Also so ganz versteh ich noch nicht, woräuf du hinaus möchtest, aber so wie ich das jetzt verstanden habe, gibt es doch insgesamt 2n! verschiedene Kombinationen. Und davon sind n! Kombinationen für Frauen und n! Kombinationen für die Männer. Mir ist auch klar, dass du bei der b darauf hinweisen willst, dass man n! als n*(n-1)*(n-2)*...*1! schreiben kann, nur irgendwie hab ich den ganzen Zusammenhang noch nicht verstanden. Besonders was ich auch mit dem hoch 2 anzufangen habe. Wäre echt nett, wenn du mir vielleicht einen genaueren Hinweis geben könntest :-D
lg penguin
|
|
|
| |
|
> Also so ganz versteh ich noch nicht, woräuf du hinaus
> möchtest, aber so wie ich das jetzt verstanden habe, gibt
> es doch insgesamt 2n! verschiedene Kombinationen. Und davon
> sind n! Kombinationen für Frauen und n! Kombinationen für
> die Männer. Mir ist auch klar, dass du bei der b darauf
> hinweisen willst, dass man n! als n*(n-1)*(n-2)*...*1!
> schreiben kann, nur irgendwie hab ich den ganzen
> Zusammenhang noch nicht verstanden. Besonders was ich auch
> mit dem hoch 2 anzufangen habe. Wäre echt nett, wenn du mir
> vielleicht einen genaueren Hinweis geben könntest :-D
Aus den insgesamt $2n=n+n$ Personen kannst Du auf [mm] $\binom{2n}{n}$ [/mm] Arten $n$ Personen auswählen. Dies ist die linke Seite der zu beweisenden Identität.
Du kannst aber eine $n$-elementige Teilmenge aus der Menge der $2n$ Personen auch so auswählen: Du wählst $k$ Männer, dies ist auf [mm] $\binom{n}{k}$ [/mm] Arten möglich, und dann wählst Du noch $n-k$ Frauen dazu, dies ist auf [mm] $\binom{n}{n-k}=\binom{n}{k}$ [/mm] Arten möglich. Summieren bezüglich $k$ von $k=0$ bis $k=n$ ergibt die rechte Seite der zu beweisenden Identität.
|
|
|
| |
|
Ich wollte nur nochmal fragen, ob die Frage nun zu deiner Zufriedenheit beantwortet ist?
|
|
|
|
![[]](/images/popup.gif){kind=small}
Vandermonde's Convolution