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

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

Hinweis: Aus Aufgabe 5: ${\begin{pmatrix}n\\k\end{pmatrix}}={\begin{pmatrix}n-1\\k-1\end{pmatrix}}+{\begin{pmatrix}n-1\\k\end{pmatrix}}$

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\rightarrow n+1$

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

$=\sum _{k=0}^{n}{\begin{pmatrix}n\\k\end{pmatrix}}x^{n+1-k}y^{k}+\sum _{k=0}^{n}{\begin{pmatrix}n\\k\end{pmatrix}}x^{n-k}y^{k+1}=$

$={\begin{pmatrix}n\\0\end{pmatrix}}x^{n+1}y^{0}+\sum _{k=1}^{n}{\begin{pmatrix}n\\k\end{pmatrix}}x^{n+1-k}y^{k}+\sum _{k=0}^{n-1}{\begin{pmatrix}n\\k\end{pmatrix}}x^{n-k}y^{k+1}+{\begin{pmatrix}n\\n\end{pmatrix}}x^{0}y^{n+1}=$

$=x^{n+1}+y^{n+1}+\sum _{k=1}^{n}{\begin{pmatrix}n\\k\end{pmatrix}}x^{n+1-k}y^{k}+\sum _{k=0}^{n-1}{\begin{pmatrix}n\\k\end{pmatrix}}x^{n-k}y^{k+1}=$

Indexverschiebung

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

$=x^{n+1}+y^{n+1}+\sum _{k=1}^{n}[{\begin{pmatrix}n\\k\end{pmatrix}}+{\begin{pmatrix}n\\k-1\end{pmatrix}}]x^{n+1-k}y^{k}=x^{n+1}+y^{n+1}+\sum _{k=1}^{n}{\begin{pmatrix}n+1\\k\end{pmatrix}}x^{n+1-k}y^{k}=$

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

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

einbinden in die Summenformel

$=\sum _{k=0}^{n+1}{\begin{pmatrix}n+1\\k\end{pmatrix}}x^{n+1-k}y^{k}$