Vollständige Induktion mit Rekursionsgleichung, Binomialkoeffizienten.

Question

Aufgabenstellung:

 Zeigen Sie, dass folgendes gilt:$$f(n,n) = \sum_{i=0}^{n-1} \begin{pmatrix} n-1 \\ i \end{pmatrix}\begin{pmatrix} n+i-1 \\ i \end{pmatrix} \quad \forall \, n \ge 1$$  Bis jetzt  hab ich raus:

1.Delannoy Numbers(Central Delannoy numbers)

2.  \(f(n,n) = f(n-1,n)+f(n,n-1)+f(n-1,n-1) \) -> Rekursionsgleichung

3. \(\sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} n+i \\ i \end{pmatrix}= f(n,n+1) + f(n+1,n) + f(n,n)\)

4.  \(\sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} n+i \\ i \end{pmatrix}= f(n,n+1) + f(n+1,n) + \sum_{i=0}^{n-1} \begin{pmatrix} n-1 \\ i \end{pmatrix}\begin{pmatrix} n+i-1 \\ i \end{pmatrix}\)

Mehr hab ich leider nicht, ich weiß nur, dass es iwas mit dem Pascalschen Dreieck und den Delannoy numbers ist.

Würde mich für jede Antwort freuen, bin echt verzweifelt.

                                                         

Comments

Was ist f(n,n) ?

Was genau sollst du zeigen? Dass die Delannoy- Zahlen mit dieser Summe berechnet werden können?

Sind 1), 2) , 3) und 4) vorausgesetzt ?

---

Das war nur ein Gedanke, ich denke nämlich, dass es was mit den Delannoy Zahlen zu tun hat.

Aus dem

f(n−1,n)+f(n,n−1)+f(n−1,n−1) 

das ist dabei f(n,n)

folgt die Formel oben

---

Was ist f(n,n) ?
Definition gegeben oder nicht?

---

So wie es da steht. Eine Definition war nicht gegeben, in der Teilaufgabe davor, haben wir jedoch die Rekursionsgleichung herausgefunden also f(n,m) welche

f(n−1,n)+f(n,n−1)+f(n−1,n−1)

ist. Ansonsten stand da

nur dass was ganz oben steht (Über delannoy numbers) mehr nicht.

"Zeigen sie dass "---" für alle n >= 1 gilt."

---

D.h. es ist bekannt, dass f(n,n) Delannoy-Zahlen sind (?)

Man muss ja wissen, was man beweisen will. :)

In deinem Link wird nichts von Induktion erwähnt. Wer verlangt einen Induktionsbeweis?

"a little algebra" weist auf eine kurze Umformung hin.

---

Ja genau. Ich hab allein für die Fragestellung Tage gebraucht....

---

Aha. Du hast dir die Frage selber gestellt?

---

Nein natürlich nicht...ich hab Tage gebraucht um sie zu verstehen...

---

Nein nein alles ab der Nummerierung ist meine Vermutung....die eigentliche Fragestellung ist darüber...

---

Nein nein alles ab der Nummerierung ist meine Vermutung....die eigentliche Fragestellung ist darüber...

Das ist leider ein Problem. Über der Nummerierung steht einfach ein f(n,n) links in der Gleichung. Die Summe daneben könnte auch die Definition von f(n,n) sein. Dann gäbe es nichts zu beweisen.

haben wir jedoch die Rekursionsgleichung herausgefunden also f(n,n) welche

f(n−1,n)+f(n,n−1)+f(n−1,n−1)

ist.

Da muss noch vorher schon mehr über f bekannt gewesen sein, sonst hättet ihr nicht herausfinden können.

---

Gegeben sei ein (allgemeines) m × n Schachbrett, wobei m, n ∈ N mit m ≥ 1 und n ≥ 1. Ein
König soll vom Feld (1, 1) (links unten) zum Feld (m, n) (rechts oben) laufen. Dabei darf er
in einem Schritt nur eine der drei folgenden Bewegungen ausführen: 
• Ein Feld vertikal nach oben laufen.
• Ein Feld horizontal nach rechts laufen.
• Ein Feld diagonal nach rechts oben laufen.
Sei f(m, n) die Anzahl möglicher Pfade, die der König auf einem m × n Schachbrett von links
unten nach rechts oben laufen kann (z.B. gilt f(2, 2) = 3).
1. Geben Sie eine rekursive Darstellung für f an und begründen Sie diese.
2. Zeigen Sie, dass f(n, n) =" das was oben steht"

Die komplette Fragestellung, mehr war nicht gegeben und die RG hab ich selbst rausgefunden

Answer 1

Wenn Du wirklich schon

$$  (3) \quad \sum_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} n+i \\ i \end{pmatrix}= f(n,n+1) + f(n+1,n) + f(n,n) $$ bewiesen hast, dann gilt doch auch

$$  (*) \quad \sum_{i=0}^{n-1} \begin{pmatrix} n-1 \\ i \end{pmatrix} \begin{pmatrix} n-1+i \\ i \end{pmatrix}= f(n-1,n) + f(n,n-1) + f(n-1,n-1) $$ und (*) ist wegen (2) doch gleich \( f(n,n) \) also zusammen

$$ f(n,n) = \quad \sum_{i=0}^{n-1} \begin{pmatrix} n-1 \\ i \end{pmatrix} \begin{pmatrix} n-1+i \\ i \end{pmatrix} $$