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

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

Induktionsanfang k=0 ist einfach...

Induktionsschritt: $k\to k+1$

Zu zeigen:

$\sum _{l=0}^{k+1}(-1{)}^l\left(\begin{array}{c}n\\ l\end{array}\right)=(-1{)}^{k+1}\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$

$\sum _{l=0}^k(-1{)}^l\left(\begin{array}{c}n\\ l\end{array}\right)+(-1{)}^{k+1}\left(\begin{array}{c}n\\ k+1\end{array}\right)=(-1{)}^{k+1}\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$

Induktionsbehauptung einsetzen:

$(-1{)}^k\left(\begin{array}{c}n-1\\ k\end{array}\right)+(-1{)}^{k+1}\left(\begin{array}{c}n\\ k+1\end{array}\right)=(-1{)}^{k+1}\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$

$-(-1{)}^{k+1}\left(\begin{array}{c}n-1\\ k\end{array}\right)+(-1{)}^{k+1}\left(\begin{array}{c}n\\ k+1\end{array}\right)=(-1{)}^{k+1}\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$

(5) einsetzen

$(-1{)}^{k+1}\left(\begin{array}{c}n-1\\ k+1\end{array}\right)=(-1{)}^{k+1}\left(\begin{array}{c}n-1\\ k+1\end{array}\right)$

qed