www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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 + Tipp
Status: (Frage) beantwortet Status 
Datum: 13:13 Sa 03.11.2012
Autor: Paetec

Aufgabe
Beweisen Sie folgende Aussage durch vollständige Induktion
und veranschaulichen Sie diesen Zusammenhang im Pascalschen Dreieck

[mm] \forall [/mm] n [mm] \in \IN \forall [/mm] k  [mm] \in \IN [/mm] : [mm] \summe_{m=0}^{k}\vektor{n + m \\ n} [/mm] = [mm] \vektor{n + k + 1 \\ n + 1} [/mm]

wir haben uns als Induktionsanfang folgendes gedacht:

[mm] \summe_{m=0}^{k}\vektor{n + m -1 \\ n} [/mm] + [mm] \vektor{n + m - 1 \\ n - 1} [/mm]

als iv sind wir dann auf

[mm] \summe_{m=0}^{k}\vektor{n + m -1 \\ n} [/mm] + [mm] \summe_{m=0}^{k} \vektor{n + m - 1 \\ n - 1} [/mm]

=

[mm] \vektor{n -1 + k + 1 \\ n -1 + 1} [/mm] + [mm] \summe_{m=0}^{k} \vektor{n + m - 1 \\ n - 1} [/mm]

gekommen. Ist das bis hierhin richtig? Wir kommen leider nicht weiter.. Vielen vielen dank für jegliche Hilfe!!

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt

        
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:28 Sa 03.11.2012
Autor: Marcel

Hallo,

> Beweisen Sie folgende Aussage durch vollständige
> Induktion
>  und veranschaulichen Sie diesen Zusammenhang im
> Pascalschen Dreieck
>  
> [mm]\forall[/mm] n [mm]\in \IN \forall[/mm] k  [mm]\in \IN[/mm] :
> [mm]\summe_{m=0}^{k}\vektor{n + m \\ n}[/mm] = [mm]\vektor{n + k + 1 \\ n + 1}[/mm]

nur mal direkt als Hinweis:
Hier macht man sozusagen "zwei Induktionen in einer":
1.) Zeige die Behauptung für [mm] $n=k=1\,.$ [/mm] (Ich nehme an, dass [mm] $\IN=\IN \setminus \{0\}$). [/mm]

2.) Halte $k [mm] \in \IN$ [/mm] als Parameter fest und führe eine Induktion über
[mm] $n\,.$ [/mm]

3.) Halte $n [mm] \in \IN$ [/mm] als Parameter fest und führe eine Induktion über [mm] $k\,.$ [/mm]

Was das bedeutet bzw. warum das funktioniert, kannst Du ja mal
versuchen, Dir klarzumachen, indem Du die Aussagen
$$A(n,k) [mm] \text{ (wir schreiben }A(n,k)\text{, wenn sie wahr ist, sonst würden wir }\neg [/mm] A(n,k) [mm] \text{ schreiben)}\,$$ [/mm]
in eine [mm] "$\IN \times \IN$" [/mm] Matrix schreibst - das [mm] $n\,$ [/mm] entspricht also der
Zeilenzahl, dass [mm] $k\,$ [/mm] der Spaltenzahl.

Wenn Du nun [mm] $A(n_0,k_0)$ [/mm] als wahr erkannt hast, dann zeigt der
Induktionsschluss $k [mm] \to k+1\,,$ [/mm] wenn er gelingt, dass alle Aussagen
"in der Zeile [mm] $n_0$ [/mm] und rechts von [mm] $k_0\,$" [/mm] wahr sind.
Analog zeigt der Induktionsschluss $n [mm] \to n+1\,,$ [/mm] dass alle Aussagen
in der Spalte [mm] $k_0$ [/mm] "unterhalb von [mm] $n_0$ [/mm] wahr sind".

Damit kannst Du Dir überlegen, dass Du damit folgern kannst, wenn Du
wie oben vorgegangen bist und Dir der Induktionsbeweis so gelungen
ist:
Alle Aussagen $A(n,k)$ mit $n [mm] \ge n_0$ [/mm] und $k [mm] \ge k_0$ [/mm] sind wahr.

Denn: Nehmen wir an, wir haben $A(N,K)$ mit $N [mm] \ge n_0$ [/mm] und $K [mm] \ge K_0\,.$ [/mm]
Gehen wir vom Eintrag der Matrix in der [mm] $n_0$-ten [/mm] Zeile und [mm] $k_0$-ten [/mm]
Spalte erst an die Stelle [mm] $A(N,k_0\,,)$ [/mm] so ist diese Aussage wahr wegen
des Induktionsschrittes $n [mm] \to n+1\,.$ [/mm]
Die Aussage [mm] $A(N,k_0)$ [/mm] ist also wahr. Wegen des Induktionsschrittes
$k [mm] \to [/mm] k+1$ können wir dann aber in der [mm] $N\,$-ten [/mm] Zeile der Matrix auch
von der [mm] $k_0$-ten [/mm] Spalte zur [mm] $K\,$-ten [/mm] Spalte gehen, und sehen so, dass
die Aussage in diesem Matrixeintrag dann wahr ist.

(Beachte: Ich gehe bei der Argumentation oben erst zeilenweise von [mm] $n_0$ [/mm]
zu [mm] $N\,$ [/mm] und dann in der [mm] $N\,$-ten [/mm] Zeile spaltenweise von [mm] $k_0$ [/mm] zu [mm] $K\,.$ [/mm]
Man könnte natürlich auch erst in der [mm] $n_0$-ten [/mm] Zeile bleiben und dann
dort von Spalte [mm] $k_0$ [/mm] zur Spalte [mm] $K\,$ [/mm] laufen und erst dann von [mm] $n_0$ [/mm]
zu [mm] $N\,.$ [/mm] Das sind die "naheliegendsten Wege". Natürlich kann man auch
auf komplizierterem Wege ausgehend von der [mm] $n_0$-ten [/mm] Zeile, [mm] $k_0$-ten [/mm]
Spalte zu dem Eintrag der Matrix [mm] $A\,$ [/mm] in der [mm] $N\,$-ten [/mm] Zeile und [mm] $K\,$-ten [/mm]
Spalte gelangen - wichtig ist einfach: Mit dem vorgeschlagenen
Induktionsprinzip "gibt es stets einen solchen Weg". (Man sollte hier
tatsächlich noch definieren, was wir hier unter "einem solchen Weg"
verstehen - wenn Du aber verstehst, was ich meine, kann ich mir das
eventuell ersparen...))

P.S. In irgendeiner Antwort, die schon länger her ist, hatte ich das ganze
Verfahren auch schonmal begründet. Mir dauert das suchen danach zu
lange - aber wenn Du magst, kannst Du ja mal danach suchen, und wenn
Du das tust und sie findest, gerne verlinken. Das wäre eigentlich so eine
Antwort gewesen, auf die ich hier einfach nochmal gerne verwiesen hätte,
die aber nicht "gut genug archiviert" für mich ist!

Gruß,
  Marcel

Bezug
                
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:25 Sa 03.11.2012
Autor: wieschoo

Ich würde mal hier behaupten, dass eine Induktion in k völlig ausreicht und man am Anfang n beliebig aber fest wählt.


Bezug
                        
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:53 Sa 03.11.2012
Autor: Marcel

Hallo wieschoo,

> Ich würde mal hier behaupten, dass eine Induktion in k
> völlig ausreicht und man am Anfang n beliebig aber fest
> wählt.

so genau habe ich mir die Aufgabe nicht angeguckt. Trotzdem ist die von
mir vorgeschlagene Methode relativ allgemeingültig. (Ob sie (hier)
umständlich(er) ist, habe ich mir gar nicht überlegt - ganz ehrlich!) ;-)  

Gruß,
  Marcel

Bezug
                                
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 01:17 So 04.11.2012
Autor: Helbig

Hallo Marcel,

> > Ich würde mal hier behaupten, dass eine Induktion in k
> > völlig ausreicht und man am Anfang n beliebig aber fest
> > wählt.
>  
> so genau habe ich mir die Aufgabe nicht angeguckt. Trotzdem
> ist die von
>  mir vorgeschlagene Methode relativ allgemeingültig. (Ob
> sie (hier)
> umständlich(er) ist, habe ich mir gar nicht überlegt -
> ganz ehrlich!) ;-)  

Wieso mußt Du da zwei Induktionen machen? Einmal nach $n$ mit $k$ als Parameter und dann nach $k$ mit $n$ als Parameter. Jeder der beiden Induktionsbeweise beweist doch dasselbe. Es liegt nahe, eine Induktion nach $k$ zu führen, schlicht weil $k$ nicht so oft wie n in der Gleichung auftaucht.

Gruß,
Wolfgang

Bezug
                                        
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:29 So 04.11.2012
Autor: Marcel

Hallo Wolfgang,

> Hallo Marcel,
>  
> > > Ich würde mal hier behaupten, dass eine Induktion in k
> > > völlig ausreicht und man am Anfang n beliebig aber fest
> > > wählt.
>  >  
> > so genau habe ich mir die Aufgabe nicht angeguckt. Trotzdem
> > ist die von
>  >  mir vorgeschlagene Methode relativ allgemeingültig.
> (Ob
> > sie (hier)
> > umständlich(er) ist, habe ich mir gar nicht überlegt -
> > ganz ehrlich!) ;-)  

>

> Wieso mußt Du da zwei Induktionen machen?

erneut: Ich habe mir da KEINE Gedanken gemacht, ob man wirklich zwei
Induktionen machen MUSS. Ich habe nur ein generelles Vorgehen
beschrieben. Man lege mir kein "das ist notwendig" hin, wenn ich nur
schreibe "das ist hinreichend". Wenn ich eine Aussage [mm] $B\,$ [/mm] beweisen
will und weiß, dass [mm] $A\,$ [/mm] und [mm] $C\,$ [/mm] gelten und dann $A [mm] \Rightarrow [/mm] B$
beweise, wird an dem Beweis nichts falsch, wenn ich zusätzlich noch
$C [mm] \Rightarrow [/mm] B$ beweise. Es ist unnötig, aber nicht falsch. Und hier
habe ich mir bei der Aufgabenstellung einfach zu wenig Gedanken gemacht
bzw. keine Gedanken gemacht, ob man eine doppelte Induktion vielleicht
doch nicht braucht. Ich verstehe gerade die Diskussion daher auch nicht
ganz - es sollte eigentlich geklärt sein, da ich das schonmal erwähnt habe!

> Einmal nach [mm]n[/mm]
> mit [mm]k[/mm] als Parameter und dann nach [mm]k[/mm] mit [mm]n[/mm] als Parameter.
> Jeder der beiden Induktionsbeweise beweist doch dasselbe.

Erneut: Ich habe nur kurz auf die Aufgabenstellung geguckt!

> Es liegt nahe, eine Induktion nach [mm]k[/mm] zu führen, schlicht
> weil [mm]k[/mm] nicht so oft wie n in der Gleichung auftaucht.

Ich widerspreche dabei ja auch niemanden. ;-)

Gruß,
  Marcel

Bezug
                                                
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:08 So 04.11.2012
Autor: wieschoo

Wir schlagen jetzt solange auf dich mit Argumenten ein, bis du jede Aufgabe in Zukunft mit einer Induktion in k löst und davon Albträume bekommst. [grins]

Bezug
                                                        
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:19 So 04.11.2012
Autor: Marcel

Hallo,

> Wir schlagen jetzt solange auf dich mit Argumenten ein, bis
> du jede Aufgabe in Zukunft mit einer Induktion in k löst
> und davon Albträume bekommst. [grins]

nnnnnnnnnnnnnnnnnneeeeeiiiiin [grins]
( Man beachte das oft vorkommende [mm] $n\,.$ [/mm] ;-) )

Gruß,
  Marcel

Bezug
        
Bezug
vollständige Induktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:30 Sa 03.11.2012
Autor: wieschoo

Ich würde mit

[mm]\sum_{m=0}^{k+1} \binom {n + m} n=\sum_{m=0}^k \binom {n + m} n + \binom {n + k + 1} n[/mm]

anfangen.

Steht da als Beweisemethode vollständige Induktion, denn es geht auch ohne.

Bezug
        
Bezug
vollständige Induktion: Induktionsvariable ?
Status: (Antwort) fertig Status 
Datum: 18:29 Sa 03.11.2012
Autor: Helbig

Hallo Paetec,

> Beweisen Sie folgende Aussage durch vollständige
> Induktion
>  und veranschaulichen Sie diesen Zusammenhang im
> Pascalschen Dreieck
>  
> [mm]\forall[/mm] n [mm]\in \IN \forall[/mm] k  [mm]\in \IN[/mm] :
> [mm]\summe_{m=0}^{k}\vektor{n + m \\ n}[/mm] = [mm]\vektor{n + k + 1 \\ n + 1}[/mm]
>  
> wir haben uns als Induktionsanfang folgendes gedacht:
>
> [mm]\summe_{m=0}^{k}\vektor{n + m -1 \\ n}[/mm] + [mm]\vektor{n + m - 1 \\ n - 1}[/mm]

Auf welche Induktionsvariable bezieht sich Eure Induktion. Wir haben hier zwei zur Auswahl nämlich k oder n.

Das verstehe ich nicht. Im Induktionsanfang muß man doch eine Aussage formulieren und dann beweisen.

>
> als iv sind wir dann auf
>
> [mm]\summe_{m=0}^{k}\vektor{n + m -1 \\ n}[/mm] + [mm]\summe_{m=0}^{k} \vektor{n + m - 1 \\ n - 1}[/mm]
>
> =
>
> [mm]\vektor{n -1 + k + 1 \\ n -1 + 1}[/mm] + [mm]\summe_{m=0}^{k} \vektor{n + m - 1 \\ n - 1}[/mm]
>
> gekommen. Ist das bis hierhin richtig?

Nein!

> Wir kommen leider
> nicht weiter.. Vielen vielen dank für jegliche Hilfe!!

Als erstes ist die Induktionsvariable festzulegen. z. B. k:

Dann ist im Induktionsanfang für alle n und k=0 zu beweisen:

[mm] $\sum_{m=0}^k [/mm] {n+m [mm] \choose [/mm] n} = {n+k + 1 [mm] \choose [/mm] n + 1}$

Setze also k=0 und rechne die Ausdrücke aus.

Im Induktionsschritt habt ihr als Induktionsvoraussetzung:

[mm] $\sum_{m=0}^k [/mm] {n+m [mm] \choose [/mm] n} = {n+k + 1 [mm] \choose [/mm] n + 1}$

und sollt hieraus

[mm] $\sum_{m=0}^{k+1} [/mm] {n+m [mm] \choose [/mm] n} = {n+k + 2 [mm] \choose [/mm] n + 1}$

folgern. Und dies für alle k und n.

Also los!

Gruß,
Wolfgang

Bezug
        
Bezug
vollständige Induktion: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 18:24 So 04.11.2012
Autor: Paetec

Vielen dank für eure hilfreichen Tips. Meine Partnerin und ich haben uns jetzt nochmal rangesetzt und sind zu folgendem Ergebnis gekommen.

Ist das jetzt so richtig? Wir sind beide noch ziemliche Anfänger auf dem Gebiet und sind uns eigentlich noch absolut unsicher..

IA: [mm] \forall [/mm] n, k = 0 zu beweisen

[mm] \summe_{m=0}^{k} \vektor{n + m \\ n} [/mm] = [mm] \vektor{n + k + 1 \\ n + 1} [/mm]  | k=0 setzen

IV: [mm] \summe_{m=0}^{k} \vektor{n + m \\ n} [/mm] = [mm] \vektor{n + k + 1 \\ n + 1} [/mm]

zu folgern: [mm] \summe_{m=0}^{k + 1} \vektor{n + m \\ n} [/mm] = [mm] \vektor{n + (k + 1) +1 \\ n + k} [/mm] = [mm] \vektor{n + k + 2 \\ n + 1} [/mm]

IB: [mm] \summe_{m=0}^{k + 1} \vektor{n + m \\ n} [/mm] = [mm] \vektor{n + k + 1 \\ n + 1} [/mm] +  [mm] \summe_{m=0}^{k + 1} [/mm] k + [mm] \vektor{n + k + 1 \\ n } [/mm]

=  [mm] \summe_{m=0}^{k + 1} [/mm] =  [mm] \summe_{m=0}^{k } [/mm] + [mm] \vektor{n + k + 1 \\ n} [/mm] = [mm] (\vektor{n + k + 1 \\ n + 1} [/mm] + [mm] \vektor{n + k + 1 \\ n}) [/mm]

n + k + 1 durch p ersetzen

=> [mm] \summe_{m=0}^{k } (\vektor{p \\ n + 1} [/mm] + [mm] \vektor{p \\ n}) [/mm]


vielen dank

Bezug
                
Bezug
vollständige Induktion: Antwort
Status: (Antwort) fertig Status 
Datum: 19:38 So 04.11.2012
Autor: Helbig


>
> IA: [mm]\forall[/mm] n, k = 0 zu beweisen
>
> [mm]\summe_{m=0}^{k} \vektor{n + m \\ n}[/mm] = [mm]\vektor{n + k + 1 \\ n + 1}[/mm]
>  | k=0 setzen

So weit so gut! Und nun muß diese Gleichung tatsächlich für $k=0$ bewiesen werden. Das fehlt noch!

Und jetzt kommt wohl schon der Induktionsschritt.

>
> IV: [mm]\summe_{m=0}^{k} \vektor{n + m \\ n}[/mm] = [mm]\vektor{n + k + 1 \\ n + 1}[/mm]

Dies ist die Induktionsvoraussetzung.

>  
> zu folgern: [mm]\summe_{m=0}^{k + 1} \vektor{n + m \\ n}[/mm] =
> [mm]\vektor{n + (k + 1) +1 \\ n + k}[/mm] = [mm]\vektor{n + k + 2 \\ n + 1}[/mm]

Genau! Aus der Induktionsvoraussetzung ist die Induktionsbehauptung zu folgern.

Aber was jetzt kommt, kann ich beim besten Willen nicht als Beweis der Induktionsbehauptung interpretieren.

>  
> IB: [mm]\summe_{m=0}^{k + 1} \vektor{n + m \\ n}[/mm] = [mm]\vektor{n + k + 1 \\ n + 1}[/mm]
> +  [mm]\summe_{m=0}^{k + 1}[/mm] k + [mm]\vektor{n + k + 1 \\ n }[/mm]
>
> =  [mm]\summe_{m=0}^{k + 1}[/mm] =  [mm]\summe_{m=0}^{k }[/mm] + [mm]\vektor{n + k + 1 \\ n}[/mm]
> = [mm](\vektor{n + k + 1 \\ n + 1}[/mm] + [mm]\vektor{n + k + 1 \\ n})[/mm]
>  
> n + k + 1 durch p ersetzen
>
> => [mm]\summe_{m=0}^{k } (\vektor{p \\ n + 1}[/mm] + [mm]\vektor{p \\ n})[/mm]

Was soll das denn?

Jetzt habt Ihr schon mal genau Eure Beweispflichten formuliert. Aber es fehlen die Beweise selbst.

Gruß,
Wolfgang

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


^ Seitenanfang ^
www.vorhilfe.de