Zeigen Sie die folgenden Aussagen für n ∈ N, 0 ≤ k n

Question

Aufgabe:

Zeigen Sie die folgenden Aussagen für n ∈ N, 0 ≤ k < n

\(\begin{pmatrix} n\\k \end{pmatrix}= \sum \limits_{i=0}^{k}\begin{pmatrix} n-k-1+i\\i \end{pmatrix}\)

Problem/Ansatz:

Ich versthe nicht wie ich das zu zeigen habe.

Comments

\(\LaTeX\) muss in \( und \) (inline) oder $$ und $$ (display) eingeschlossen werden, damit es gerendert wird.

Answer 1

Vollständige Induktion über \(n\) in Verbindung mit dem Pascalschen Dreieck

        \({n\choose k} = {{n-1}\choose{k-1}} + {{n-1}\choose k}\).

Comments

danke! Aber wie sieht dann der nächste Schritt aus? Ich habe schon den I.A , die I.V nur beim I.S stecke ich leider fest...

$$\begin{pmatrix} n\\k+1 \end{pmatrix}= \sum \limits_{i=0}^{k+1}\begin{pmatrix} n-k-2+i\\i \end{pmatrix}$$

---

Das sieht wie eine vollständige Induktion über \(k\) aus.

Mache eine vollständige Induktion über \(n\).

\(\begin{aligned}&\sum \limits_{i=0}^{k}\begin{pmatrix} (n+1)-k-1+i\\i \end{pmatrix}\\ =& \sum \limits_{i=0}^{k-1}\begin{pmatrix} n-(k-1)-1+i\\i \end{pmatrix} + \begin{pmatrix} n\\k \end{pmatrix}\\ =&\dots\\ =&{{n+1}\choose k}\end{aligned}\)