vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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]](/images/smileys/grins.gif "[grins]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
|
