Aufgaben zum Thema Kombinatorik

Gib die Koeffizienten des Polynoms $(1 + x)^{n}$ mittels Binomialkoeffizienten an und zeige durch geschickes Verwenden dieser Formel

$\sum_{k=0}^n\binom{n}{k} = 2^n$ und, falls n>0, $\sum_{k=0}^n(-1)^k\binom{n}{k} = 0$

Für diese Aufgabe benötigst Du folgendes Grundwissen: Kombinatorik

Zuerst geben wir die Koeffizienten von $(x + 1)^{n}$ an (Beweis ist der Vollständigkeit angehängt; laut der Aufgabenstellung reicht das bloße Angeben):

\displaystyle (x+1)^n=\sum_{k=0}^n{\begin{pmatrix}n\\k\end{pmatrix}x^k}

Nun versuchen wir, darüber $2^{n}$ darzustellen:

\displaystyle 2^n=(1+1)^n=\sum_{k=0}^n{\begin{pmatrix}n\\k\end{pmatrix}1^k}=\sum_{k=0}^n{\begin{pmatrix}n\\k\end{pmatrix}}\\\blacksquare

Ähnlich verfahren wir mit der zweiten angegebenen Gleichung (mit der Bedingung $n > 0$ ):

\displaystyle 0=0^n=(1-1)^n=\sum_{k=0}^n{(-1)^k\begin{pmatrix}n\\k\end{pmatrix}}\\\blacksquare

Anhang

Zuerst müssen wir

\displaystyle \begin{pmatrix}n\\k-1\end{pmatrix}+\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}n+1\\k\end{pmatrix}

zeigen:

\displaystyle \begin{pmatrix}n\\k-1\end{pmatrix}+\begin{pmatrix}n\\k\end{pmatrix}=\frac{n!}{(k-1)!(n-(k-1))!}+\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}\cdot\frac{1}{n-k+1}+\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}\cdot\frac{k}{k}\cdot\frac{1}{n-k+1}+\frac{n!}{k!(n-k)!}=\frac{n!}{k(k-1)!(n-k)!}\cdot\frac{k}{n-k+1}+\frac{n!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}\cdot\frac k{n-k+1}+\frac{n!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}(1+\frac k{n-k+1})=\frac{n!}{k!(n-k)!}(\frac{n-k+1}{n-k+1}+\frac k{n-k+1})=\frac{n!}{k!(n-k)!}\cdot\frac{n+1}{n-k+1}=\frac{(n+1)!}{k!((n+1)-k)!}=\begin{pmatrix}n+1\\k\end{pmatrix}

Mit dieser Gleichung können wir nun einen Induktionsbeweis führen mit der Induktionsvoraussetzung:

\displaystyle (x+1)^n=\sum_{k=0}^n{\begin{pmatrix}n\\k\end{pmatrix}x^k},n\in\mathbb{N_0}

Beginnen wir bei $n = 0$ und betrachten auch $n = 1$ :

\displaystyle (x+1)^0=1=\begin{pmatrix}0\\0\end{pmatrix}

\displaystyle (x+1)^1=x+1=\begin{pmatrix}1\\0\end{pmatrix}x+\begin{pmatrix}1\\1\end{pmatrix}

Nun können wir den Induktionsschritt von $n\rightarrow n+1$ durchführen:

\displaystyle (x+1)^{n+1}=(x+1)(x+1)^n\overset{IV}=(x+1)\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k=x\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k+\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k=\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^{k+1}+\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k=\sum_{k=1}^{n+1}\begin{pmatrix}n-1\\k\end{pmatrix}x^k+\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}x^k=\begin{pmatrix}n\\n\end{pmatrix}x^{n+1}+\begin{pmatrix}n\\0\end{pmatrix}x^0+\sum_{k=1}^n(\begin{pmatrix}n\\k\end{pmatrix}+\begin{pmatrix}n\\k-1\end{pmatrix})x^k=\begin{pmatrix}n+1\\n+1\end{pmatrix}x^{n+1}+\begin{pmatrix}n+1\\0\end{pmatrix}x^0+\sum_{k=1}^n\begin{pmatrix}n+1\\k\end{pmatrix}x^k=\sum_{k=0}^{n+1}\begin{pmatrix}n+1\\k\end{pmatrix}x^k\\\blacksquare

Hast du eine Frage oder Feedback?

Bitte melde dich an, um diese Funktion zu benutzen.