Catalan-Zahlen und Beweis

Question

Aufgabe:

Hey zuerst haben wir die Catalan Zahlen durch C0 := 1 fur alle n >= 1 definiert.

\( C_{n}:=\sum \limits_{k=0}^{n-1} C_{k} \cdot C_{n-1-k} \)

rekusiv

Wir soll beweisen dass fur alle n >= 1

\( 2 \cdot \sum \limits_{k=0}^{n-1} 3^{k}=3^{n}-1 \)

gilt.

Problem/Ansatz:

Ich kenne mich mit Catalan Zahlen garnicht aus. Kann mir vielleicht wer erkláren, inwiefern ich das bearbeiten soll. Vielleicht eine Webseite wo ich es nachlesen kann, um zu verstehen was von mir verlangen wird. Ich habe dazu nur was in Wiki gelesen aber komme trdz nicht weiter. Danke im Voraus...

Answer 1

Aloha :)

$$2\cdot\sum\limits_{k=0}^{n-1}3^k=(3-1)\cdot\sum\limits_{k=0}^{n-1}3^k=3\cdot\sum\limits_{k=0}^{n-1}3^k-1\cdot\sum\limits_{k=0}^{n-1}3^k=\sum\limits_{k=0}^{n-1}3^{k+1}-\sum\limits_{k=0}^{n-1}3^k$$$$\phantom{2\cdot\sum\limits_{k=0}^{n-1}3^k}=\sum\limits_{k=1}^{n}3^k-\sum\limits_{k=0}^{n-1}3^k=\left(3^n+\sum\limits_{k=1}^{n-1}3^k\right)-\left(3^0+\sum\limits_{k=1}^{n-1}3^k\right)=3^n-1$$

Answer 2

Das geht auch ganz ohne den Begriff der Catalanzahlen und nur mit Rückgriff auf die Summenformel einer geometrischen Reihe mit dem konstanten Quotienten q=3 und dem Startglied 1.

Comments

kannst du es vielleicht expliziter erkláren)

---

Schlage die Summenformel für geometrische Reihen in einer Formelsammlung nach, setze a=1 und q=3 und vergleiche mit dem, was du beweisen willst.