Ramsey - obere Grenzen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:45 Di 08.09.2009 | | Autor: | BlaaacK |
| Aufgabe | Aus der "Pascal"-Rekursion R(k,l) [mm] \le [/mm] R(k-1,l) + R(k,l-1) und den Anfangsbedingungen erkennen wir sofort
R(k,l) [mm] \le \vektor{k+l-2 \\ k-1} [/mm] |
Mir ist nicht klar, wieso man das sofort erkennen sollte. Ich steh da irgendwie auf dem Schlauch...
Bisher habe ich folgendes selbst probiert:
R(k,l) [mm] \le [/mm] R(k-1,l) + R(k,l-1)
[mm] \le \vektor{k-1+l-2 \\ k-1-1} [/mm] + [mm] \vektor{k+l-1-2 \\ k-1}
[/mm]
= [mm] \vektor{k+l-3 \\ k-2} [/mm] + [mm] \vektor{k+l-3 \\ k-1}
[/mm]
= [mm] \vektor{k+l-2 \\ k-1}
[/mm]
Aber reicht das als Beweis? Doch eher nicht... Habe ja bisher nur die Formel angewandt.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:01 Di 08.09.2009 | | Autor: | felixf |
Hallo!
> Aus der "Pascal"-Rekursion R(k,l) [mm]\le[/mm] R(k-1,l) + R(k,l-1)
> und den Anfangsbedingungen erkennen wir sofort
>
> R(k,l) [mm]\le \vektor{k+l-2 \\ k-1}[/mm]
> Mir ist nicht klar, wieso
> man das sofort erkennen sollte. Ich steh da irgendwie auf
> dem Schlauch...
>
> Bisher habe ich folgendes selbst probiert:
>
> R(k,l) [mm]\le[/mm] R(k-1,l) + R(k,l-1)
> [mm]\le \vektor{k-1+l-2 \\ k-1-1}[/mm] + [mm]\vektor{k+l-1-2 \\ k-1}[/mm]
>
> = [mm]\vektor{k+l-3 \\ k-2}[/mm] + [mm]\vektor{k+l-3 \\ k-1}[/mm]
>
> = [mm]\vektor{k+l-2 \\ k-1}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> Aber reicht das als Beweis? Doch eher nicht... Habe ja
> bisher nur die Formel angewandt.
Nun, du musst es noch in das "Framework" einer doppelten Induktion setzen: erstmal Induktion nach $k$ (die Aussage gelte fuer ein $k$ und dort fuer alle $l$), dann (im Induktionsschritt) Induktion nach $l$ (oder umgekehrt).
Und du musst halt noch den Induktionsanfang machen jeweils, das sollten genau die oben genannten Anfangsbedingungen sein.
LG Felix
|
|
|
|
