matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-Analysis-InduktionVollständige Induktion
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Uni-Analysis-Induktion" - Vollständige Induktion
Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Vollständige Induktion: Korrektur
Status: (Frage) beantwortet Status 
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

        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:45 So 18.11.2012
Autor: Maurizz

muss ich nochmal überarbeiten
Bezug
                        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Vollständige Induktion: Formel ist falsch!
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 16:48 So 18.11.2012
Autor: reverend

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


Bezug
                
Bezug
Vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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)

Bezug
                        
Bezug
Vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]

Bezug
                        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 17:40 So 18.11.2012
Autor: reverend

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


Bezug
                                
Bezug
Vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]

Bezug
                                        
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
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

>  
>
>  


Bezug
                                        
Bezug
Vollständige Induktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]


Bezug
                                                
Bezug
Vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                
Bezug
Vollständige Induktion: Einfache Induktion genügt
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]