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$$