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

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

Hinweis: Aus Aufgabe 5: $\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n-1\\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\\ k\end{array}\right)$

sowie $(x+y{)}^n=(x+y{)}^{n-1}(x+y)$

Induktionsanfang $n=0$ ist trivial,

Induktionsannahme ist die obige Formel (welche es zu beweisen gilt),

Induktionsschritt: $n\to n+1$

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

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

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

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

Indexverschiebung

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

$=x^{n+1}+y^{n+1}+\sum _{k=1}^n[\left(\begin{array}{c}n\\ k\end{array}\right)+\left(\begin{array}{c}n\\ k-1\end{array}\right)]x^{n+1-k}{y}^k=x^{n+1}+y^{n+1}+\sum _{k=1}^n\left(\begin{array}{c}n+1\\ k\end{array}\right)x^{n+1-k}{y}^k=$

Andere Darstellung für $x^{n+1}$ und $y^{n+1}$

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

einbinden in die Summenformel

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