Zeigen Sie n+1 über k+1

Question

Seien \( n, k \in \mathbb{N} \) und \( k \leq n . \) Zeigen Sie:
\( \left(\begin{array}{l} n+1 \\ k+1 \end{array}\right)=\sum \limits_{m=k}^{n}\left(\begin{array}{l} m \\ k \end{array}\right) \)

Ich weiß, dass ich das Umformen muss, aber ich weiß nicht wie.

Answer 1

1) Die Aufggabe klingt nach Induktion.

2) Im Pascalschen Dreieck gilt \( \begin{pmatrix} n\\k \end{pmatrix} \) + \( \begin{pmatrix} n\\k+1 \end{pmatrix} \)=\( \begin{pmatrix} n+1\\k+1 \end{pmatrix} \)

Auf dieser Grundlage kannst du während der Induktion \( \begin{pmatrix} n+2\\k+1 \end{pmatrix} \) auch als Summe von zwei Binomialkoeffizienten schreiben.

Answer 2

Hallo,

Der Beweis läuft über Vollständige Induktion.

Zeige zunächst, dass obige Gleichung für \(n=k\) gilt. Anschließend kommt dann der Schritt von \(n\) nach \(n+1\):$$\begin{aligned} {n+2 \choose k+1} &= { n+1 \choose k } + {n+1 \choose k+1} && \left| \, {}^{*)}\right. \\ &= { n+1 \choose k } + \sum_{m=k}^n { m\choose k}  \\ &=  \sum_{m=k}^{n+1} { m\choose k} \\ &\text{q.e.d.}\end{aligned}$$*) siehe Rekursive Darstellung und Pascalsches Dreieck.

Comments

Ich verstehe nicht ganz wie ich den Induktionsanfang in dem Fall mache. Also, da würde ich ja normalerweise n = 1 (oder 0) setzen und dass dann ausrechnen. Aber wenn ich das mit n=k mache müsste ich das dann nicht nochmal für k>n machen?

---

In Deiner Aufgabe steht \(k \le n\). Das ist Voraussetzung! Und \(k \gt n\) macht auch nicht viel Sinn, wenn da ein Ausdruck wie \({n+1 \choose k+1}\) steht.

Du zeigst den Induktionsanfang auch nicht für \(n=1\), sondern für \(n=k\). Dies ist der größte Wert, den \(k\) annehmen kann und umgekehrt ist es auch der kleinste Wert, den \(n\) annehmen kann!

Es gilt stets $${n \choose n} = {n+1 \choose n+1} = 1$$