vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:39 Di 22.03.2011 | | Autor: | bandchef |
| Aufgabe | Zeigen Sie mit vollständiger Induktion über n, dass für jedes $m [mm] \in \mathbb [/mm] N$ (fest vorgegeben für jedes $n [mm] \in \mathbb N_0$ [/mm] gilt:
[mm] $\summe_{k=0}^{n}\vektor{m+k \\ k} [/mm] = [mm] \vektor{m+n+1 \\ n}$ [/mm] |
Hi Leute!
Könnt ihr mir bei dier Aufgabe helfen? Ich weiß, dass man mit einem Induktionsanfang anfängt. Man schaut quasi was für n=0 auf der linken Seite und auf der rechten Seite rauskommt. Aber wie geht's da dann weiter?
(IA) n=0:
[mm] $\text{LS} [/mm] = [mm] \summe_{k=0}^{0}\vektor{... \\ ...} [/mm] = [mm] \text{?}$
[/mm]
[mm] $\text{RS} [/mm] = [mm] \vektor{... \\ ...} [/mm] = [mm] \text{?}$
[/mm]
Ich hab quasi Probleme weil ich nicht weiß was ich mit m machen soll...
Könnt ihr mir helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:43 Di 22.03.2011 | | Autor: | Loddar |
Hallo bandchef!
Das [mm]m_[/mm] kannst Du jeweils stehen lassen.
Du brauchst hier lediglich einen Spezialfall des ![[]](/images/popup.gif) Binomialkoeffizienten mit:
[mm]\vektor{j\\
0} \ = \ 1[/mm]
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:47 Di 22.03.2011 | | Autor: | bandchef |
D.h. so ist das schon mal richtig:
$ [mm] \text{LS} [/mm] = [mm] \summe_{k=0}^{0}\vektor{m+k \\ k} [/mm] = [mm] \vektor{m \\ 0}$
[/mm]
$ [mm] \text{RS} [/mm] = [mm] \vektor{m+1 \\ 0}$
[/mm]
Stimmt das soweit? Aber normalerweise mus doch RS = LS sein, was aber hier jetzt nicht ist...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:48 Di 22.03.2011 | | Autor: | Loddar |
Hallo bandchef!
Hast Du meine Antwort oben auch gelesen?
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:50 Di 22.03.2011 | | Autor: | bandchef |
Ja ich hab deine Antwort gelesen und das was ich dir dann geantwortet habe ist, das was ich durch deine Antwort gemeint habe richtig umsetzen zu können...
|
|
|
| |
|
Moin bandchef,
> D.h. so ist das schon mal richtig:
>
> [mm]\text{LS} = \summe_{k=0}^{0}\vektor{m+k \\ k} = \vektor{m \\ 0}[/mm]
>
> [mm]\text{RS} = \vektor{m+1 \\ 0}[/mm]
>
>
> Stimmt das soweit? Aber normalerweise mus doch RS = LS
> sein, was aber hier jetzt nicht ist...
Doch, es gilt [mm] \vektor{m\\0}=\vektor{m+1\\0}=1
[/mm]
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:51 Di 22.03.2011 | | Autor: | bandchef |
Laut kamaleonti ist das jetzt so richtig:
$ [mm] \text{LS} [/mm] = [mm] \summe_{k=0}^{0}\vektor{m+k \\ k} [/mm] = [mm] \vektor{m \\ 0} [/mm] = 1 $
$ [mm] \text{RS} [/mm] = [mm] \vektor{m+1 \\ 0} [/mm] = 1$
stimmt das jetzt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:52 Di 22.03.2011 | | Autor: | Loddar |
Hallo!
Ja, das stimmt immer noch!
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:59 Di 22.03.2011 | | Autor: | bandchef |
Na, dann ist ja der IA abgeschlossen. Nun folgt doch dann der IS.
Was muss ich hier nun tun?
$ [mm] \underbrace{\summe_{k=0}^{n}\vektor{m+k \\ k} = \vektor{m+n+1 \\ n}}_{IV} \Rightarrow \summe_{k=0}^{n+1}\vektor{m+k \\ k} [/mm] = [mm] \vektor{m+(n+1)+1 \\ n+1}$
[/mm]
Ist das soweit richtig?
|
|
|
| |
|
Hallo bandchef,
> Na, dann ist ja der IA abgeschlossen. Nun folgt doch dann
> der IS.
>
> Was muss ich hier nun tun?
>
>
> [mm]\underbrace{\summe_{k=0}^{n}\vektor{m+k \\ k} = \vektor{m+n+1 \\ n}}_{IV} \Rightarrow \summe_{k=0}^{n+1}\vektor{m+k \\ k} = \vektor{m+(n+1)+1 \\ n+1}[/mm]
>
Die rechte Seite ist doch zu zeigen.
Um das zu zeigen, mußt Du die IV ins Spiel bringen:
[mm]\summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ n+1}= \ ...[/mm]
>
> Ist das soweit richtig?
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:26 Di 22.03.2011 | | Autor: | bandchef |
Das muss aber schon so lauten, oder:
$ [mm] \summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ \red{ n}}= [/mm] \ ... $
Was muss ich da jetzt bei den 3 Punkten einsetzen? Das verstehe ich noch nicht ganz!
|
|
|
| |
|
Hallo bandchef,
> Das muss aber schon so lauten, oder:
>
> [mm]\summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ \red{n }}= \ ...[/mm]
Das ist schon richtig. wie ich geschrieben habe:
[mm]\summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ \blue{n+1} }= \ ...[/mm]
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:32 Di 22.03.2011 | | Autor: | bandchef |
Ok, kannst du mir dann auch erklären warum das richtig? Und vielleicht auch gleich nochmal draufhelfen wie es dann weiter geht? Diesen Schritt hab ich noch nicht so ganz verstanden...
Stimmts vielleicht so:
$ [mm] \summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ n+1}= \vektor{m+n+1 \\ n}+\vektor{m+n+1 \\ n+1} [/mm] = ...$
|
|
|
| |
|
Hallo bandchef,
> Ok, kannst du mir dann auch erklären warum das richtig?
> Und vielleicht auch gleich nochmal draufhelfen wie es dann
> weiter geht? Diesen Schritt hab ich noch nicht so ganz
> verstanden...
Das ist richtig, weil das dieselbe Summe ist.
Ersetze die linke Seite der IV durch
die rechte Seite der IV und addiere das.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:42 Di 22.03.2011 | | Autor: | bandchef |
Oh, ich glaube da hat sich jetzt grad dummerweise ein Edit von mir überschnitten. Ich hab das jetzt so gemacht:
$ [mm] \summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ n+1}= \vektor{m+n+1 \\ n}+\vektor{m+n+1 \\ n+1} [/mm] = ... $
Ist das richtig?
|
|
|
| |
|
Hallo bandchef,
> Oh, ich glaube da hat sich jetzt grad dummerweise ein Edit
> von mir überschnitten. Ich hab das jetzt so gemacht:
>
> [mm]\summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ n+1}= \vektor{m+n+1 \\ n}+\vektor{m+n+1 \\ n+1} = ...[/mm]
>
> Ist das richtig?
Ja, das ist richtig.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:48 Di 22.03.2011 | | Autor: | bandchef |
Gut, dann ist es ja schon mal gar nicht so schlecht.
Jetzt muss ich doch durch weitere Umformung auf auf das kommen, was im (IS) nach dem [mm] $\Rightarrow$ [/mm] steht, oder?
Wie aber geht man mit solchen Binomialkoeffizienten um? Wie darf ich die jetzt miteinander verrechnen?
$ [mm] \summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ n+1} \overbrace{=}^{IV} \vektor{m+n+1 \\ n}+\vektor{m+n+1 \\ n+1} [/mm] = [mm] \vektor{2m+2n+2 \\ 2n+1} [/mm] $
So stimmt das nicht oder?
|
|
|
| |
|
Hallo, das sieht ja bitter böse aus, wende die Definition [mm] \vektor{n\\k}=\bruch{n!}{k!*(n-k)!} [/mm] an
(i) [mm] \vektor{m+n+1\\n}=\bruch{(m+n+1)!}{n!*(m+1)!}
[/mm]
(ii) [mm] \vektor{m+n+1\\n+1}=\bruch{(m+n+1)!}{(n+1)!*m!}
[/mm]
jetzt erweitere (i) mit (n+1) und (ii) mit (m+1), dann alls auf einen Bruchstrich
Steffi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:28 Di 22.03.2011 | | Autor: | bandchef |
Die Definition war mir natürlich bekannt. Was mir auch klar ist, dass man den Binomialkoeffizienten durch die Definition ersetzen kann. Aber, was mir überhaupt nicht klar ist, wie du auf den Nenner kommst... Der Zähler ist mir klar. Das k! in der Definition nimmt quasi den "oberen Eintrag" das jeweiligen Binomialkoeffizienten auf.
Aber wie kommt man auf den Nenner?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:54 Di 22.03.2011 | | Autor: | Marcel |
Hallo,
> Die Definition war mir natürlich bekannt. Was mir auch
> klar ist, dass man den Binomialkoeffizienten durch die
> Definition ersetzen kann. Aber, was mir überhaupt nicht
> klar ist, wie du auf den Nenner kommst... Der Zähler ist
> mir klar. Das k! in der Definition nimmt quasi den "oberen
> Eintrag" das jeweiligen Binomialkoeffizienten auf.
>
> Aber wie kommt man auf den Nenner?
da ich die vorherige Ausführung nur "sporadisch" gelesen habe, hoffe ich, gerade auch die passende Antwort zu geben:
Du schreibst [mm] $(n+1)!=n!*(n+1)\,$ [/mm] und [mm] $(m+1)!=m!*(m+1)\,.$ [/mm] Der Rest ist nichts anderes wie "auf Hauptnenner bringen".
Übrigens mal ein Tipp zu "solchen Induktionsbeweisen mit Gleichheit":
Es ist durchaus legitim, sich mal hinzuschreiben, "was rauskommen soll" und das ganze dann durch Äquivalenzumformungen nachzurechnen. (Andernfalls sollte man sich halt zwischendurch klarmachen, wie man mit dem, was man bisher gemacht hat, zum Ziel kommen kann.)
Wie ich das meine zeige ich mal an einem bekannten Beispiel:
Es ist [mm] $1+\ldots+n=(n/2)*(n+1)\,$ [/mm] für alle natürlichen [mm] $n\,.$
[/mm]
Beweis:
Induktionsanfang ist klar, und im Induktionsschritt nehmen wir an, es sei [mm] $n\,$ [/mm] gefunden mit
[mm] $$1+\ldots+n=(n/2)(n+1)\,.$$
[/mm]
Dann GILT nach Induktionsvoraussetzung
[mm] $$(\star)\;\;1+\ldots+n+(n+1)=(n/2)*(n+1)+(n+1)\,.$$
[/mm]
Was wir zeigen wollen [mm] ($\overset{!}{=}$ [/mm] bedeutet: "wir hätten gern"), ist
[mm] $$1+\ldots+n+(n+1)\overset{!}{=}((n+1)/2)*((n+1)+1)$$
[/mm]
bzw.
[mm] $$(\star_2)\;\;1+\ldots+n+(n+1)\overset{!}{=}((n+1)/2)*(n+2)\,.$$
[/mm]
Jetzt gibt es zwei Möglichkeiten, dies anzugehen:
1. Möglichkeit:
Wir schauen uns die rechte Seite von [mm] $(\star)$ [/mm] an und überlegen uns, wie wir diesen Term so umformen können, dass wir die rechte Seite von [mm] $(\star_2)$ [/mm] erhalten. Man kann dies zum Beispiel so machen, dass man in [mm] $(\star)$ [/mm] den Faktor [mm] $(n+1)\,$ [/mm] vorklammert.
2. Möglichkeit:
Wir BEHAUPTEN zunächst einfach, dass die rechte Seite von [mm] $(\star)$ [/mm] auch mit der rechten Seite von [mm] $(\star_2)$ [/mm] übereinstimmt. Das heißt, wir wollen darauf hinaus, dass
$$(n/2)*(n+1)+(n+1) [mm] \overset{!}{=}((n+1)/2)*(n+2)\,.$$
[/mm]
Dazu rechnen wir
[mm] $$(n/2)*(n+1)+(n+1)=((n+1)/2)*(n+2)\,.$$
[/mm]
[mm] $$\gdw [/mm] n(n+1)+2*(n+1)=(n+1)(n+2)$$
[mm] $$\gdw n^2+3n+2=n^2+3n+2$$
[/mm]
[mm] $$\gdw 0=0\,.$$
[/mm]
Durch Lesen der letzten Umformungen von [mm] $0=0\,$ [/mm] ausgehend, von unten nach oben unter Benutzung der "Implikationen [mm] $\Leftarrow$", [/mm] erhalten wir somit die Gültigkeit der Gleichung
[mm] $$(n/2)*(n+1)+(n+1)=((n+1)/2)*(n+2)\,,$$
[/mm]
also genau das, was wir gebraucht hatten.
(Siehe oben: Wir hätten ja gerne $(n/2)*(n+1)+(n+1) [mm] \overset{!}{=}((n+1)/2)*(n+2)\,$ [/mm] gehabt, und nun haben wir das auch!)
P.S.:
Diese "wir behaupten, dass das, was wir brauchen, auch gilt und versuchen es nachzuweisen"-Methode kann manchmal schiefgehen, wenn man "mehr fordert als man wirklich braucht". Ansonsten ist halt zu beachten, dass man manchmal die Äquivalenzumformungen abbricht und zu einer Aussage gelangt, deren Wahrheitsgehalt man gerne einsehen würde - und um diesen einzusehen, kann es sein, dass man dafür nur noch Folgerungen der Richtung [mm] "$\Leftarrow$" [/mm] und "Lesen der Implikationskette von unten nach oben" benutzt, wo ganz unten bei dieser Implikationskette eine (bekanntlich oder offensichtlich) wahre Aussage stehen soll. Derartiges kann etwa bei Ungleichungen, die induktiv zu beweisen sind, auftreten. Aber evtl. wirst Du das auch bald kennenlernen...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:40 Di 22.03.2011 | | Autor: | bandchef |
Du schreibst, ich soll erweitern. Das sieht jetzt so aus:
$ ... = [mm] \bruch{(m+n+1)!}{n!\cdot{}(m+1)!} \cdot \frac{n+1}{n+1} [/mm] + [mm] \bruch{(m+n+1)!}{(n+1)!\cdot{}m!} \cdot \frac{m+1}{m+1} [/mm] = ...$
Aber irgendwie kann ich doch jetzt trotzdem nicht auf einen Bruch zusammenfassen, oder?
|
|
|
| |
|
Hallo
bedenke n!*(n+1)=(n+1)! und m!*(m+1)=(m+1)!
[mm] \bruch{(m+n+1)!}{n!*(m+1)!}*\bruch{n+1}{n+1}+\bruch{(m+n+1)!}{(n+1)!*m!}*\bruch{m+1}{m+1}
[/mm]
[mm] =\bruch{(m+n+1)!*(n+1)+(m+n+1)!*(m+1)}{(n+1)!*(m+1)!}
[/mm]
im Zähler ausklammern
[mm] =\bruch{(m+n+1)!*(n+1+m+1)}{(n+1)!*(m+1)!}
[/mm]
[mm] =\bruch{(m+n+1)!*(m+n+2)}{(n+1)!*(m+1)!}
[/mm]
[mm] =\bruch{(m+n+2)!}{(n+1)!*(m+1)!}
[/mm]
[mm] =\vektor{m+n+2 \\ n+1}
[/mm]
q.e.d.
Steffi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:15 Di 22.03.2011 | | Autor: | bandchef |
Zitat: "bedenke n!*(n+1)=(n+1)! und m!*(m+1)=(m+1)! "
Das verstehe ich nicht. Kannst du das ausführlicher erläutern?
Deswegen ist mir (wahrscheinlich) auch nicht klar, wie du auf die zwei unteren Brüche kommst. Wie kommst du auf die Idee, den ersten Nenner in den zweiten Nenner umzuwandeln? Das hat doch mit der oberen in meinem Zitat stehenden Definition was zu tun, oder?
$... = [mm] \bruch{(m+n+1)!}{n!\cdot{}(m+1)!}\cdot{}\bruch{n+1}{n+1}+\bruch{(m+n+1)!}{(n+1)!\cdot{}m!}\cdot{}\bruch{m+1}{m+1} [/mm] $
$ [mm] =\bruch{(m+n+1)!\cdot{}(n+1)+(m+n+1)!\cdot{}(m+1)}{(n+1)!\cdot{}(m+1)!} [/mm] = ... $
Wie kommst des Weiteren auf:
$... [mm] =\bruch{(m+n+2)!}{(n+1)!\cdot{}(m+1)!} [/mm] $
$ [mm] =\vektor{m+n+2 \\ n+1} [/mm] $
Wie kommst du hier dann wieder darauf den Nenner so umzuwandeln und dann als "unteres Element" im Binomialkoeffizient einzusetzen? Nun gut, weil's ja so sein muss, aber warum, wie kommst du drauf?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:43 Di 22.03.2011 | | Autor: | gnom347 |
siehe unten
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:15 Mi 23.03.2011 | | Autor: | Marcel |
Hallo,
> Zitat: "bedenke n!*(n+1)=(n+1)! und m!*(m+1)=(m+1)! "
>
> Das verstehe ich nicht. Kannst du das ausführlicher
> erläutern?
das ist ganz einfach:
Es gilt
[mm] $$(n+1)!=\underbrace{1*2*\ldots*(n-1)*n}_{=n!}\;\;*\;\;(n+1)=n!*(n+1)=(n+1)*n!\,.$$
[/mm]
Beispiel:
$$n=6:$$
Dann ist
[mm] $$7!=1*2*3*4*5*6*7=6!*7=7*6!\,.$$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:48 Di 22.03.2011 | | Autor: | bandchef |
Stimmt es so:
$ [mm] \summe_{k=0}^{n+1}\vektor{m+k \\ k}=\summe_{k=0}^{n}\vektor{m+k \\ k}+\vektor{m+n+1 \\ n+1} \overbrace{=}^{IV} \vektor{m+n+1 \\ n}+\vektor{m+n+1 \\ n+1} [/mm] = ... = [mm] \frac{(m+n+1)! \left((n+1)!m!+n!(m+1)!\right)}{n!(m+1)! \cdot (n+1)!m!}$
[/mm]
|
|
|
| |
|
Hallo, nein, siehe meine andere Antwort, Steffi
|
|
|
|
