Zusatzaufgabe: Vollständige Induktion und Binomialkoeffizient

 

Beweisen Sie die folgende Gleichung mit Hilfe der vollständigen Induktion:

\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} = 2^n

Lösung

Induktionsanfang:

n:0 \to \sum\limits_{k = 0}^0 {\left( {\begin{array}{*{20}{c}} 0 \\ k \\ \end{array} } \right)} = \left( {\begin{array}{*{20}{c}} 0 \\ 0 \\ \end{array} } \right) = 1 = 2^0

Induktionsschritt:

Zuerst senken wir die obere Grenze der Summe von n+1 auf n:

n:n+1 \to \sum\limits_{k = 0}^{n+1} {\left( {\begin{array}{*{20}{c}} n+1 \\ k \\ \end{array} } \right)} = \left( {\begin{array}{*{20}{c}} n+1 \\ n+1 \\ \end{array} } \right)+\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n+1 \\ k \\ \end{array} } \right)}

In einem späteren Schritt brauchen wir den Summanden für k=0 außerhalb der Summe, er wird daher vorgezogen:

\left( {\begin{array}{*{20}{c}} n+1 \\ n+1 \\ \end{array} } \right)+\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n+1 \\ k \\ \end{array} } \right)} = \left( {\begin{array}{*{20}{c}} n+1 \\ n+1 \\ \end{array} } \right)+\left( {\begin{array}{*{20}{c}} n+1 \\ 0 \\ \end{array} } \right)+\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{c}} n+1 \\ k \\ \end{array} } \right)}

Die beiden vorgezogenen Summanden sind = 1. Um der Induktionsannahme näher zu kommen, brauchen wir ein (n über k) in der Summe. Dies lässt sich nicht ohne weiteres erreichen, daher teilen wir die Summe zunächst in zwei Teilsummen auf:

1+1+\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{c}} n+1 \\ k \\ \end{array} } \right)} = 1+1+\sum\limits_{k = 1}^n {\left[ {\left( {\begin{array}{*{20}{c}} n \\ k-1 \\ \end{array} } \right)+\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} \right]}

= 1+1+\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{c}} n \\ k-1 \\ \end{array} } \right)} +\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)}

Wir wollen nun den Inhalt beider Summen auf (n über k) bringen. Dazu müssen wir bei der linken Summe die untere Grenze von 1 auf 0 ändern. Dadurch wird aus dem k-1 ein k. Allerdings würde so ein Summand mehr in der Summe sein. Um das zu verhindern, senken wir n auf n-1:

1+1+\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{c}} n \\ k-1 \\ \end{array} } \right)} +\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} = 1+1+\sum\limits_{k = 0}^{n-1} {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} +\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)}

Zuletzt müssen nun noch die Grenzen der Summen auf 0 bis n geändert werden. In der linken Summe fehlt dazu der Summand (n über n). Dieser ist =1, wir verwenden daher einer der beiden vorgezogenen 1en. Bei der rechten Summe fehlt der Summand (n über 0). Da auch dieser =1 ist, verwenden wir die zwiete vorgezogene 1. Wir erhalten:

\left( {\begin{array}{*{20}{c}} n \\ n \\ \end{array} } \right)+\left( {\begin{array}{*{20}{c}} n \\ 0 \\ \end{array} } \right)+\sum\limits_{k = 0}^{n-1} {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} +\sum\limits_{k = 1}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} +\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)}

Hier kann nun endlich die Induktionsannahme eingesetzt werden:

\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} +\sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right)} = 2^n +2^n = 2 \cdot 2^n = 2^{n+1}

q.e.d.

Ähnliche Artikel

Kommentar verfassen