TU Wien:Diskrete Mathematik für Informatik UE (Drmota)/Übungen WS10/Beispiel 8

Beweis von $\sum _{l=0}^{k}(-1)^{l}{\begin{pmatrix}n\\l\end{pmatrix}}=(-1)^{k}{\begin{pmatrix}n-1\\k\end{pmatrix}}$ durch Vollständige Induktion.

Induktionsanfang k=0 ist einfach...

Induktionsschritt: $k\rightarrow k+1$

Zu zeigen:

$\sum _{l=0}^{k+1}(-1)^{l}{\begin{pmatrix}n\\l\end{pmatrix}}=(-1)^{k+1}{\begin{pmatrix}n-1\\k+1\end{pmatrix}}$

$\sum _{l=0}^{k}(-1)^{l}{\begin{pmatrix}n\\l\end{pmatrix}}+(-1)^{k+1}{\begin{pmatrix}n\\k+1\end{pmatrix}}=(-1)^{k+1}{\begin{pmatrix}n-1\\k+1\end{pmatrix}}$

Induktionsbehauptung einsetzen:

$(-1)^{k}{\begin{pmatrix}n-1\\k\end{pmatrix}}+(-1)^{k+1}{\begin{pmatrix}n\\k+1\end{pmatrix}}=(-1)^{k+1}{\begin{pmatrix}n-1\\k+1\end{pmatrix}}$

$-(-1)^{k+1}{\begin{pmatrix}n-1\\k\end{pmatrix}}+(-1)^{k+1}{\begin{pmatrix}n\\k+1\end{pmatrix}}=(-1)^{k+1}{\begin{pmatrix}n-1\\k+1\end{pmatrix}}$

(5) einsetzen

$(-1)^{k+1}{\begin{pmatrix}n-1\\k+1\end{pmatrix}}=(-1)^{k+1}{\begin{pmatrix}n-1\\k+1\end{pmatrix}}$

qed