Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:06 So 18.11.2012 | | Autor: | Maurizz |
| Aufgabe | a) Für alle p, q ∈ N mit p ≥ q gilt:
[mm] \summe_{j=q-1}^{p-1}\pmat{ j \\ q - 1} [/mm] = [mm] \pmat{ p \\ q} [/mm] |
Ich möchte mich vergewissern, dass ich es nicht missverstehe.
Wenn p = 5 ist, dann summiere ich doch abhängig von q:
Für q = 3;
[mm] \summe_{j=3-1}^{5-1}
[/mm]
[mm] \pmat{2\\2}+\pmat{3\\2}+\pmat{4\\2} [/mm] = [mm] \pmat{5\\3}
[/mm]
Für Induktionsanfang wähle ich dann p,q = 1.
[mm] \summe_{j=1-1}^{1-1}\pmat{0\\0} [/mm] = [mm] \pmat{1\\1}
[/mm]
Induktionsvoraussetzung ist [mm] \summe_{j=q-1}^{p-q}\pmat{ j \\ q - 1} [/mm] = [mm] \pmat{ p \\ q} \forall_{p,q}\in\IN [/mm] : q [mm] \le [/mm] p
Um es zu beweisen reicht es ,denke ich, p+1 zu wählen.
Also lautet meine Behauptung:
[mm] \summe_{j=q-1}^{p}\pmat{j\\q-1}=\pmat{p+1\\q}
[/mm]
[mm] \pmat{p+1\\q} [/mm] = [mm] \bruch{(p+1)!}{q!((p+1)-q)!}
[/mm]
Und dort gelange ich hin durch:
[mm] \bruch{p!}{q!(p-q)!} [/mm] + ?
Ist es überhaupt noch legal bis hierhin?
Da fällt mir gerade auf, ich kann j mit q-1 ersetzen für die Rechnung.
[mm] \bruch{p!}{q!(p-q)!} [/mm] + [mm] \pmat{q-1\\q-1}. [/mm] Aber [mm] \pmat{q-1\\q-1} [/mm] wäre immer 1
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:33 So 18.11.2012 | | Autor: | Helbig |
> a) Für alle p, q ∈ N mit p ≥ q gilt:
>
> [mm]\summe_{j=q-1}^{p-q}\pmat{ j \\ q - 1}[/mm] = [mm]\pmat{ p \\ q}[/mm]
>
>
> Ich möchte mich vergewissern, dass ich es nicht
> missverstehe.
>
> Wenn p = 5 ist, dann summiere ich doch abhängig von q:
> Für q = 3;
>
>
> [mm]\summe_{j=3-1}^{5-1}[/mm]
>
> [mm]\pmat{2\\2}+\pmat{3\\2}+\pmat{4\\2}[/mm] = [mm]\pmat{5\\3}[/mm]
Dies ist schon mal richtig!
Für den Induktionsbeweis solltest Du zuerst festlegen, welche der beiden Variablen p oder q die Induktionsvariable sein soll. Da p seltener in der Formel auftaucht, schlage ich p vor. Dann ist im Induktionsanfang p=1 zu setzen. Da q [mm] $\le$ [/mm] p ist, ist auch q=1.
>
> Für Induktionsanfang wähle ich dann p,q = 1.
Genau!
>
> [mm]\summe_{j=1-1}^{1-1}\pmat{0\\0}[/mm] = [mm]\pmat{1\\1}[/mm]
>
> Induktionsvoraussetzung ist [mm]\summe_{j=q-1}^{p-q}\pmat{ j \\ q - 1}[/mm]
> = [mm]\pmat{ p \\ q} \forall_{p,q}\in\IN[/mm] : q [mm]\le[/mm] p
>
> Um es zu beweisen reicht es ,denke ich, p+1 zu wählen.
>
> Also lautet meine Behauptung:
>
> [mm]\summe_{j=q-1}^{p}\pmat{j\\q-1}=\pmat{p+1\\q}[/mm]
Nein. Du mußt auch über dem Summenzeichen p durch p+1 ersetzen. Und diese Formel mußt Du für alle q [mm] $\le$ [/mm] p+1 nachweisen. Du hast also zwei Fälle: q [mm] $\le$ [/mm] p, dann und nur dann kannst Du die Induktionsvoraussetzung verwenden. Im anderen Fall ist q=p+1 und diesen kannst Du nur ohne Induktionsvoraussetzung zeigen.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:45 So 18.11.2012 | | Autor: | Maurizz |
muss ich nochmal überarbeiten
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:49 So 18.11.2012 | | Autor: | Helbig |
> Das bedeutet also:
>
> [mm]\summe_{j=p}^{p+1}\pmat{p+1\\p}[/mm] +
> [mm]\summe_{j=q-1}^{p}\pmat{p+1\\q}[/mm]
Verstehe ich jetzt nicht. Was bedeutet was? Beachte auch meine Mitteilung.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:48 So 18.11.2012 | | Autor: | Helbig |
> a) Für alle p, q ∈ N mit p ≥ q gilt:
>
> [mm]\summe_{j=q-1}^{p-q}\pmat{ j \\ q - 1}[/mm] = [mm]\pmat{ p \\ q}[/mm]
Dies gilt z. B. nicht für p=q=2.
Links steht dann 0 (die leere Summe) und rechts steht 1.
Gruß,
Wolfgang
|
|
|
| |
|
Hallo Maurizz,
ich bin so noch nicht einverstanden.
> a) Für alle p, q ∈ N mit p ≥ q gilt:
>
> [mm]\summe_{j=q-1}^{p-q}\pmat{ j \\
q - 1}[/mm] = [mm]\pmat{ p \\
q}[/mm]
Das möchte ich bezweifeln.
Die obere Additionsgrenze der Summe stimmt nicht.
> Ich möchte mich vergewissern, dass ich es nicht
> missverstehe.
>
> Wenn p = 5 ist, dann summiere ich doch abhängig von q:
> Für q = 3;
>
>
> [mm]\summe_{j=3-1}^{5-1}[/mm]
Das stimmt nicht mit der zu zeigenden Formel überein. Hier müsste es dann [mm] \summe_{j=3-1}^{5\blue{-3}}\vektor{j\\2} [/mm] heißen!
> [mm]\pmat{2\\
2}+\pmat{3\\
2}+\pmat{4\\
2}[/mm] = [mm]\pmat{5\\
3}[/mm]
Das kann man leicht nachrechnen. Da steht 1+3+6=10.
Für die Formel, die Du in der Aufgabenstellung abgetippt hast, ergäbe sich allerdings nur:
[mm] \vektor{2\\2}=\vektor{5\\3}, [/mm] also 1=10.
Gehe ich recht in der Annahme, dass "oben auf der Summe" eigentlich $p-1$ steht?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:52 So 18.11.2012 | | Autor: | Maurizz |
ja da steht p-1, kleiner Tippfehler(die 1 und die q sind ziemlich nah:D)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:56 So 18.11.2012 | | Autor: | Marcel |
Hallo,
> ja da steht p-1, kleiner Tippfehler(die 1 und die q sind
> ziemlich nah:D)
na, dann hab' ich Dir das mal korrigiert!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:15 So 18.11.2012 | | Autor: | Maurizz |
So korregiert sieht es natürlich so aus:
[mm] \summe_{j=q-1}^{p-1}\pmat{j\\q-1}=\pmat{p\\q}=\bruch{p!}{q!(p-q)!}
[/mm]
Hier setze ich p+1 ein:
[mm] \summe_{j=q-1}^{(p+1)-1}\pmat{j\\q-1}=\pmat{p+1\\q}=\bruch{(p+1)!}{q!((p+1)-q)!}
[/mm]
Mein Ziel ist es von [mm] \bruch{p!}{q!(p-q)!} [/mm] auf [mm] \bruch{(p+1)!}{q!((p+1)-q)!} [/mm] zu gelangen.
[mm] \summe_{j=q-1}^{(p+1)-1}\pmat{j\\q-1} [/mm] = [mm] \summe_{j=q-1}^{p-1}\pmat{j\\q-1} [/mm] + [mm] \summe_{j=p-1}^{p}\pmat{j\\p-1}
[/mm]
|
|
|
| |
|
Hallo,
> So korrigiert sieht es natürlich so aus:
>
> [mm]\summe_{j=q-1}^{p-1}\pmat{j\\
q-1}=\pmat{p\\
q}=\bruch{p!}{q!(p-q)!}[/mm]
Das wäre die Induktionsannahme. Gibt es schon einen Induktionsanfang? Du hast hier ja zwei Variable.
> Hier setze ich p+1 ein:
>
> [mm]\summe_{j=q-1}^{(p+1)-1}\pmat{j\\
q-1}=\pmat{p+1\\
q}=\bruch{(p+1)!}{q!((p+1)-q)!}[/mm]
Das ist zu zeigen.
> Mein Ziel ist es von [mm]\bruch{p!}{q!(p-q)!}[/mm] auf
> [mm]\bruch{(p+1)!}{q!((p+1)-q)!}[/mm] zu gelangen.
Das nennt man Induktionsschluss.
> [mm]\summe_{j=q-1}^{(p+1)-1}\pmat{j\\
q-1}[/mm] =
> [mm]\summe_{j=q-1}^{p-1}\pmat{j\\
q-1}[/mm] +
> [mm]\summe_{j=p-1}^{p}\pmat{j\\
p-1}[/mm]
Nein, das ist falsch.
[mm] \summe_{j=q-1}^{(p+1)-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\summe_{j=q-1}^{p-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\vektor{p\\q}=\vektor{p+1\\q}
[/mm]
1. Gleichheitszeichen: letztes Glied aus der Summe gelöst und nach vorn gestellt.
2. Gleichheitszeichen: Induktionsannahme verwendet.
3. Gleichheitszeichen: Grundregel Binomialkoeffizienten [mm] \vektor{n\\k}+\vektor{n\\k+1}=\vektor{n+1\\k+1}
[/mm]
So, das heißt jetzt aber "nur", dass die Formel für ein festes q stimmt - wenn sie dann für ein bestimmtes [mm] p_0 [/mm] gilt, dann auch für alle [mm] p>p_0.
[/mm]
Jetzt fehlt noch die Induktion über q.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:20 So 18.11.2012 | | Autor: | Maurizz |
[mm] \summe_{j=q}^{p-1}\pmat{j\\q}=\pmat{p\\q+1} [/mm] + [mm] \summe_{j=q-1}^{p-1} \pmat{j\\q-1}=\pmat{p\\q+1}+\pmat{p\\q}=\pmat{p\\q+2}
[/mm]
??
[mm] \summe_{j=q-1}^{(p+1)-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\summe_{j=q-1}^{p-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\vektor{p\\q}=\vektor{p+1\\q}
[/mm]
Mir kommt es hier vor als ob man zuviel summieren würde.
Am Anfang stand doch da von j=q-1 bis p-1
Hier summieren wir dann (j=q-1 bis p-1)+(j=q-1 bis p). Geht das nicht zuweit?
Und das ist dann wohl der Grund wieso wir mit q ebenfalls den Induktionsschritt machen? Quasi um nachzurücken?
Ich nehme an man kann nicht einfach gleichzeitig p+1 und q+1 einsetzen?
Ich verstehe mittlerweile garnicht mehr was ich hier beweisen will.
Etwa zum einen das [mm] \bruch{(p+1)!}{q!((p+1)-q)!}
[/mm]
dann das [mm] \bruch{p!}{(q+1)!(p-(q+1))}!
[/mm]
Und somit etwa das [mm] \bruch{(p+1)!}{(q+1)!((p+1)-(q+1))!}?[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:31 So 18.11.2012 | | Autor: | Helbig |
> [mm]\summe_{j=q}^{p-1}\pmat{j\\q}=\pmat{p\\q+1}[/mm] +
> [mm]\summe_{j=q-1}^{p-1} \pmat{j\\q-1}=\pmat{p\\q+1}+\pmat{p\\q}=\pmat{p\\q+2}[/mm]
>
> ??
>
> [mm]\summe_{j=q-1}^{(p+1)-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\summe_{j=q-1}^{p-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\vektor{p\\q}=\vektor{p+1\\q}[/mm]
>
> Mir kommt es hier vor als ob man zuviel summieren würde.
> Am Anfang stand doch da von j=q-1 bis p-1
> Hier summieren wir dann (j=q-1 bis p-1)+(j=q-1 bis p).
> Geht das nicht zuweit?
>
> Und das ist dann wohl der Grund wieso wir mit q ebenfalls
> den Induktionsschritt machen? Quasi um nachzurücken?
>
> Ich nehme an man kann nicht einfach gleichzeitig p+1 und
> q+1 einsetzen?
Nein. Siehe meine erste Antwort in dieser Diskussion und meine letzte Mitteilung.
Gruß,
Wolfgang
>
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:43 So 18.11.2012 | | Autor: | Maurizz |
Ihr habt mich jetzt total durcheinander gebracht.
Wenn ich nur p+1 beweisen soll, dann ist
[mm] \summe_{j=q-1}^{(p+1)-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\summe_{j=q-1}^{p-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\vektor{p\\q}=\vektor{p+1\\q}
[/mm]
doch schon der beweis, weil [mm] \vektor{p+1\\q} [/mm] ausgeschrieben doch das hier ist
[mm] \bruch{(p+1)!}{q!((p+1)-q)!}
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:50 So 18.11.2012 | | Autor: | Helbig |
> Ihr habt mich jetzt total durcheinander gebracht.
Das tut mir jetzt aber leid!
>
> Wenn ich nur p+1 beweisen soll, dann ist
>
> [mm]\summe_{j=q-1}^{(p+1)-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\summe_{j=q-1}^{p-1}\vektor{j\\q-1}=\vektor{p\\q-1}+\vektor{p\\q}=\vektor{p+1\\q}[/mm]
Diese Formel mußt Du für p+1 und alle q [mm] $\le$ [/mm] p+1 zeigen. Aber die Induktionsvoraussetzung kannst Du nur für alle q [mm] $\le$ [/mm] p anwenden, nicht für q=p+1.
Dies mußt Du ohne Induktionsvoraussetzung extra zeigen. Aber auch das ist nicht schwierig.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:28 So 18.11.2012 | | Autor: | Helbig |
Hallo reverend,
> Jetzt fehlt noch die Induktion über q.
Nein. Wir machen hier eine Induktion über p der Aussage:
Für alle p und alle q [mm] $\le$ [/mm] p gilt die Formel F(p, q).
Die Induktionsbehauptung lautet dann:
Für alle q [mm] $\le$ [/mm] p+1 gilt die Formel F(p+1, q).
Und die Induktionsvoraussetzung:
Für alle q [mm] $\le$ [/mm] p gilt die Formel F(p,q).
Dies beschert uns allerdings eine Fallunterscheidung beim Beweis der Induktionsbehauptung:
Fall 1: q= p+1. Dann können wir die Induktionsvoraussetzung nicht benutzen.
Fall 2: q < p+1. Dann ist q [mm] $\le$ [/mm] p und die Induktionsvoraussetzung kann benutzt werden.
Diese Fallunterscheidung hätten wir vermeiden können, wenn wir als Induktionsvariable q gewählt hätten.
Grüße,
Wolfgang
|
|
|
|
